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(){25     q.push(1);26     memset(d, 0, sizeof(d));27     d[1]=1;28     while(!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){33               d[v]=d[u]+1;34               q.push(v);35            }36     } 37     if(!d[n])  return false;38     return true;39 }40 41 LL dfs(int u, LL flow){42     if(u==n) return flow;43     for(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        } 51     return 0;52 }53 54 void Dinic(){55     LL flow;56      while(bfs()){//利用bfs构造好层次图，这样dfs在寻找阻塞流的时候，就不会盲目的寻找了！ 57         while(flow=dfs(1, INF)) maxFlow+=flow;//利用构造好的层次图不断的寻找阻塞流！ 58     }59 }60 61 int main(){62     while(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     }74     return 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)                  25          if(!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(){37     maxFlow=0;38     while(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){50          memset(cap, 0, sizeof(cap));51          while(m--){52             int u, v;53             LL w;54             scanf("%d%d%I64d", &u, &v, &w);55             cap[u][v]+=w;  56          }57          EK();58          printf("%I64d\n", maxFlow);59    }60    return 0;    61 }