1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 int G[300][300];
5 int Prev[300]; //路径上每个节点的前驱节点
6 bool Visited[300];
7 int n,m; //m是顶点数目，顶点编号从1开始 1是源，m是汇, n是 边数
8
9 int Augment()
10 {
11 int v;
12 int i;
13 deque<int> q;
14 memset(Prev,0,sizeof(Prev));
15 memset(Visited,0,sizeof(Visited));
16 Prev[1] = 0;
17 Visited[1] = 1;
18 q.push_back(1);
19 bool bFindPath = false;
20 //用bfs寻找一条源到汇的可行路径
21 while (!q.empty())
22 {
23 v = q.front();
24 q.pop_front();
25 for (i = 1; i <= m; i++)
26 {
27 if (G[v][i] > 0 && Visited[i] == 0)
28 {
29 //必须是依然有容量的边，才可以走
30 Prev[i] = v;
31 Visited[i] = 1;
32 if( i == m )
33 {
34 bFindPath = true;
35 q.clear();
36 break;
37 }
38 else
39 q.push_back(i);
40 }
41 }
42 }
43
44 if (!bFindPath)
45 return 0;
46 int nMinFlow = 999999999;
47 v = m; //寻找源到汇路径上容量最小的边，其容量就是此次增 加的总流量
48 while( Prev[v] )
49 {
50 nMinFlow = min( nMinFlow,G[Prev[v]][v]);
51 v = Prev[v];
52 }
53 //沿此路径添加反向边，同时修改路径上每条边的容量
54 v = m;
55 while( Prev[v] )
56 {
57 G[Prev[v]][v] -= nMinFlow;
58 G[v][Prev[v]] += nMinFlow;
59 v = Prev[v];
60 }
61 return nMinFlow;
62 }
63
64 int main()
65 {
66 while (cin >> n >> m)
67 {
68 //m是顶点数目，顶点编号从1开始
69 int i,j,k;
70 int s,e,c;
71 memset( G,0,sizeof(G));
72 for( i = 0;i < n;i ++ )
73 {
74 cin >> s >> e >> c;
75 G[s][e] += c; //两点之间可能有多条边
76 }
77 int MaxFlow = 0;
78 int aug;
79 while( aug = Augment() )
80 MaxFlow += aug;
81 cout << MaxFlow << endl;
82 }
83 return 0;
84 }
