1 #include<iostream>  2 #include<cstring> 3 #include<string> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7  8 int n, m, flow; 9 int vis[205];10 //路径记录11 int pre[205];12 //邻接表13 int G[205][205];14 15 void Maxflow()16 {17     for (;;)18     {19         memset(vis, 0, sizeof(vis));20         queue<int> q;21         q.push(1);22         vis[1] = 1;23         while (!q.empty())24         {25             int x = q.front();26             q.pop();27             //到达终点28             if (x == m)  break;29             for (int i = 1; i <= m; i++)30             {31                 if (!vis[i] && G[x][i] > 0)32                 {33                     vis[i] = 1;34                     q.push(i);35                     //记录好路径36                     pre[i] = x;37                 }38             }39         }40         //没有找到增广路41         if (!vis[m])  break;42         int _min = 1000000;43         for (int i = m; i != 1; i = pre[i])44             _min = min(_min, G[pre[i]][i]);45         for (int i = m; i != 1; 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     while (cin >> n >> m)58     {59         int u, v, w;60         memset(G, 0, sizeof(G));61         for (int i = 0; i < n; i++)62         {63             cin >> u >> v >> w;64             //因为可能存在重边的情况65             G[u][v] += w;66         }67         flow = 0;68         Maxflow();69         cout << flow << endl;70     }71 }