1 //一般增广路，每次不断在生于网络找层次网络，直到找不到说明已找到最大流量 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <iostream> 6 const int N = 210; 7 using namespace std; 8  9 int n,m;10 int cap[N][N] , flow[N][N] , lev[N];11 int pre[N];//回溯标记12 13 bool find_levelnet()14 {15     memset(pre , -1 , sizeof(pre));16     queue<int> q;17     q.push(1);18     pre[1] = 0;19     memset(lev , 0x3f , sizeof(lev));20     lev[1] = 1;21     while(!q.empty()){22         int u = q.front();23         q.pop();24         for(int i=1 ; i<=n ; i++){25             int tmp = cap[u][i] - flow[u][i];26             if(tmp && lev[i] > lev[u]+1){27                 lev[i] = lev[u]+1;28                 pre[i] = u;29                 q.push(i);30             }31         }32     }33     if(lev[n] > n) return false;34     return true;35 }36 37 int get_min_flow()38 {39     int minn = 0x3f3f3f3f;40     for(int i = n ; i!=1 ; i=pre[i]){41         int u = pre[i];42         minn = min(minn , cap[u][i] - flow[u][i]);43     }44     return minn;45 }46 47 void update(int d)48 {49     for(int i = n ; i!=1 ; i=pre[i]){50         int u = pre[i];51         flow[u][i] += d;52         flow[i][u] -= d;53     }54 }55 56 int main()57 {58     //freopen("a.in","rb",stdin);59     int u,v,d;60     while(scanf("%d%d" , &m , &n) == 2){61         memset(cap , 0 ,sizeof(cap));62         memset(flow , 0 ,sizeof(flow));63         for(int i=0 ; i<m ; i++){64             scanf("%d%d%d" , &u , &v , &d);65             cap[u][v] += d; //可能有重边不断叠加66         }67 68         int ans = 0;69         while(find_levelnet()){70             int min_flow = get_min_flow();71             ans += min_flow;72             update(min_flow);73         }74 75         printf("%d\n",ans);76     }77     return 0;78 }