poj1273 Drainage Ditches 基础网络流

 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 }