首页 > 代码库 > poj 1273 Drainage Ditches 基础网络流
poj 1273 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 }
poj 1273 Drainage Ditches 基础网络流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。