poj1273Drainage Ditches

1 #include<iostream> 2 /* 3题意：就是寻找从源点到汇点的最大流！ 4 要注意的是每两个点的流量可能有多个，也就是说有重边，所以要把两个点的所有的流量都加起来 5 就是这两个点之间的流量了！ 6 7思路：建图之后直接套用最大流算法（EK, 或者是Dinic算法） 图解Dinic算法流程！

8 */ 9 #include<queue>10 #include<cstring>11 #include<cstdio>12 #include<algorithm>13 #define INF 0x3f3f3f3f3f3f3f3f14 #define N 205 15 using namespace std;16 typedef long long LL;17 LL cap[N][N];18 19 int m, n;20 LL maxFlow;21 int d[N];22 queue<int>q;23 24 bool bfs(){25q.push(1);26memset(d, 0, sizeof(d));27d[1]=1;28while(!q.empty()){29 int u=q.front();30 q.pop();31 for(int v=1; v<=n; ++v)32 if(!d[v] && cap[u][v]>0){33d[v]=d[u]+1;34q.push(v);35 }36} 37if(!d[n]) return false;38return true;39 }40 41 LL dfs(int u, LL flow){42if(u==n) return flow;43for(int v=1; v<=n; ++v)44 if(d[v]==d[u]+1 && cap[u][v]>0){45 LL a=dfs(v, min(flow, cap[u][v]));46 if(a==0) continue;//如果a==0 说明没有找到从起点到汇点的增广路， 然后换其他路接着寻找！ 47 cap[u][v]-=a;48 cap[v][u]+=a;49 return a;50 } 51return 0;52 }53 54 void Dinic(){55LL flow;56while(bfs()){//利用bfs构造好层次图，这样dfs在寻找阻塞流的时候，就不会盲目的寻找了！ 57 while(flow=dfs(1, INF)) maxFlow+=flow;//利用构造好的层次图不断的寻找阻塞流！ 58}59 }60 61 int main(){62while(scanf("%d%d", &m, &n)!=EOF){63 memset(cap, 0, sizeof(cap));64 while(m--){65 int u, v;66 LL w;67 scanf("%d%d%lld", &u, &v, &w);68 cap[u][v]+=w;69 }70 maxFlow=0;71 Dinic();72 printf("%lld\n", maxFlow);73}74return 0;75 }

1 //EK算法同样搞定 2 #include<iostream> 3 #include<queue> 4 #include<cstdio> 5 #include<cstring> 6 #include<algorithm> 7 #define INF 0x3f3f3f3f 8 using namespace std; 9 typedef __int64 LL;10 LL cap[205][205];11 int pre[205];12 LL a[205];13 int m, n;14 queue<int>q;15 LL maxFlow;16 bool spfa(){17 while(!q.empty()) q.pop();18 memset(a, 0, sizeof(a));19 q.push(1);20 a[1]=INF;21 while(!q.empty()){22 int u=q.front();23 q.pop();24 for(int v=1; v<=n; ++v) 25if(!a[v] && cap[u][v]>0){26 pre[v]=u;27 a[v]=min(a[u], cap[u][v]);28 q.push(v); 29}30 if(a[n]) break;31 } 32 if(!a[n]) return false;33 return true;34 }35 36 void EK(){37maxFlow=0;38while(spfa()){39 int u=n;40 maxFlow+=a[n];41 while(u!=1){42 cap[pre[u]][u]-=a[n];43 cap[u][pre[u]]+=a[n]; 44 u=pre[u];45 } 46}47 }48 int main(){49 while(scanf("%d%d", &m, &n)!=EOF){50memset(cap, 0, sizeof(cap));51while(m--){52 int u, v;53 LL w;54 scanf("%d%d%I64d", &u, &v, &w);55 cap[u][v]+=w; 56}57EK();58printf("%I64d\n", maxFlow);59 }60 return 0; 61 }