1003 Universal Travel Sites (35分)

题目传送门：1003 Universal Travel Sites (35分)

一、题目大意

二、解题思路

网络流问题，第一次尝试，看了刘汝佳的《算法竞赛入门经典》上的例子和代码，理解了后自己写了出来，居然真的AC了，😆😝☺️

三、AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5000;
struct Edge{
  int from, to, cap, flow;
  Edge(int from, int to, int cap, int flow):from(from), to(to), cap(cap), flow(flow){}
};
map<string, int>Map;
vector<Edge>edges;
vector<int>G[N];
void addEdge(int from, int to, int cap, int flow){
  edges.push_back(Edge(from, to, cap, 0));// 正向边
  edges.push_back(Edge(to, from, 0, 0)); // 反向边
  int cnt = edges.size();
  G[from].push_back(cnt-2);// 记住每条邻边的编号
  G[to].push_back(cnt-1);
}
int main(){
  freopen("input.txt", "r", stdin);
  int no = 1, startNo = 1, endNo = 2;
  string stra, strb;
  cin >> stra >> strb;
  Map[stra] = no++;
  Map[strb] = no++;
  int n;
  cin >> n;
  int x;
  for(int i = 0; i < n; i++){
    cin >> stra >> strb >> x;
    if(!Map[stra])
      Map[stra] = no++;
    if(!Map[strb])
      Map[strb] = no++;
    addEdge(Map[stra], Map[strb], x, 0);
  }
  int flow = 0;
  for(;;){
    int a[no], father[no];
    memset(a, 0, sizeof(a));
    memset(father, 0, sizeof(father));
    a[startNo] = INT32_MAX;
    queue<int>Q;
    Q.push(startNo);
    while(!Q.empty()){
      int head = Q.front();
      Q.pop();
      for(int i = 0; i < G[head].size(); i++){
        Edge& e = edges[G[head][i]];
        if(!a[e.to] and e.flow < e.cap){
          a[e.to] = min(a[head], e.cap - e.flow);
          father[e.to] = G[head][i];
          Q.push(e.to);
        }
      }
      if(a[endNo]){// 终点
        break;// 完成一次增广路径
      }
    }
    if(!a[endNo]){
      break;// 无法再增广，退出循环
    }
    for(int u = endNo; u != startNo; u = edges[father[u]].from){
      edges[father[u]].flow += a[endNo];
      edges[father[u]^1].flow -= a[endNo];
    }
    flow += a[endNo];
  }
  cout << flow << endl;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/104330078