[USACO09JAN]Total Flow

OJ题号：

BZOJ3996、洛谷2936、SPOJ-MTOTALF、SCU3353

思路：

题目的要求是将所有边合并成一条边，求合并后的流量。
实际上相当于直接求最大流。
EdmondsKarp模板即可。

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 6 const int V=52,E=700,s=0,t=25,inf=0x7fffffff;
 7 inline int idx(const char ch) {
 8     return (ch<='Z')?(ch-'A'):(ch-'a'+26);
 9 }
10 struct Edge {
11     int from,to,remain;
12 };
13 int sz=0;
14 Edge e[E<<1];
15 std::vector<int> g[V];
16 inline void add_edge(const int u,const int v,const int c) {
17     e[sz]=(Edge){u,v,c};
18     g[u].push_back(sz);
19     sz++;
20 }
21 int p[V],a[V];
22 inline int Augment() {
23     memset(a,0,sizeof a);
24     a[s]=inf;
25     std::queue<int> q;
26     q.push(s);
27     while(!q.empty()) {
28         int x=q.front();
29         q.pop();
30         for(unsigned i=0;i<g[x].size();i++) {
31             Edge &y=e[g[x][i]];
32             if(!a[y.to]&&y.remain) {
33                 p[y.to]=g[x][i];
34                 a[y.to]=std::min(a[x],y.remain);
35                 q.push(y.to);
36             }
37         }
38         if(a[t]) break;
39     }
40     return a[t];
41 }
42 inline int EdmondsKarp() {
43     int maxflow=0;
44     while(int flow=Augment()) {
45         for(int i=t;i!=s;i=e[p[i]].from) {
46             e[p[i]].remain-=flow;
47             e[p[i]^1].remain+=flow;
48         }
49         maxflow+=flow;
50     }
51     return maxflow;
52 }
53 int main() {
54     std::ios_base::sync_with_stdio(false);
55     std::cin.tie(NULL);
56     int n;
57     std::cin>>n;
58     for(int i=0;i<n;i++) {
59         char u,v;
60         int c;
61         std::cin>>u>>v>>c;
62         add_edge(idx(u),idx(v),c);
63         add_edge(idx(v),idx(u),0);
64     }
65     std::cout<<EdmondsKarp()<<std::endl;
66     return 0;
67 }