UVa 820 因特网带宽（最大流）

题意：

给出所有计算机之间的路径和路径容量后求出两个给定结点之间的流通总容量。

思路：

裸的最大流问题。注意有个比较坑的地方，最后需要多输出一个空行，否则会wa。

 1 #include<iostream> 
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 
 7 const int maxn = 400;
 8 
 9 int n, m;
10 int s, e;
11 int G[maxn][maxn];
12 int vis[maxn];
13 int pre[maxn];
14 int flow;
15 
16 void Maxflow()
17 {
18     flow = 0;
19     for (;;)
20     {
21         memset(vis, 0, sizeof(vis));
22         memset(pre, 0, sizeof(pre));
23         queue<int> Q;
24         Q.push(s);
25         vis[s] = 1;
26         while (!Q.empty())
27         {
28             int x = Q.front();
29             Q.pop();
30             if (x == e)  break;
31             for (int i = 1; i <= n; i++)
32             {
33                 if (!vis[i] && G[x][i] > 0)
34                 {
35                     vis[i] = 1;
36                     Q.push(i);
37                     pre[i] = x;
38                 }
39             }
40         }
41         if (!vis[e])  break;
42         int _min = 1000000;
43         for (int i = e; i != s; i = pre[i])
44             _min = min(_min, G[pre[i]][i]);
45         for (int i = e; i != s; i = pre[i])
46         {
47             G[i][pre[i]] += _min;
48             G[pre[i]][i] -= _min;
49         }
50         flow += _min;
51     }
52 }
53 
54 int main()
55 {
56     //freopen("D:\txt.txt", "r", stdin);
57     int kase = 0;
58     while (~scanf("%d",&n) && n)
59     {
60         memset(G, 0, sizeof(G));
61         cin >> s >> e >> m;
62         int x, y, c;
63         for (int i = 0; i < m; i++)
64         {
65             cin >> x >> y >> c;
66             G[x][y] += c;
67             G[y][x] = G[x][y];   //因为双向，所以得加上这个
68         }
69         Maxflow();
70         cout << "Network " << ++kase << endl;
71         cout << "The bandwidth is " << flow << "." << endl << endl;  //坑点，多输出一个空行
72     }
73 }