首页 > 代码库 > poj1273 Drainage Ditches
poj1273 Drainage Ditches
思路:
Edmonds-Karp最大流模板。
实现:
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 using namespace std; 6 7 const int INF = 0x3f3f3f3f; 8 int m, n, x, y, c; 9 int G[205][205], pre[205]; 10 bool vis[205]; 11 12 int argument() 13 { 14 queue<int> q; 15 q.push(1); 16 memset(pre, 0, sizeof(pre)); 17 memset(vis, 0, sizeof(vis)); 18 vis[1] = true; 19 bool flag = false; 20 while (!q.empty()) 21 { 22 int tmp = q.front(); 23 q.pop(); 24 for (int i = 1; i <= n; i++) 25 { 26 if (G[tmp][i] && !vis[i]) 27 { 28 pre[i] = tmp; 29 vis[i] = true; 30 if (i == n) 31 { 32 flag = true; 33 while (!q.empty()) 34 { 35 q.pop(); 36 } 37 break; 38 } 39 else 40 q.push(i); 41 } 42 } 43 } 44 if (!flag) 45 { 46 return 0; 47 } 48 int now = n; 49 int minn = INF; 50 while (pre[now]) 51 { 52 minn = min(minn, G[pre[now]][now]); 53 now = pre[now]; 54 } 55 now = n; 56 while (pre[now]) 57 { 58 G[pre[now]][now] -= minn; 59 G[now][pre[now]] += minn; 60 now = pre[now]; 61 } 62 return minn; 63 } 64 int main() 65 { 66 while (cin >> m >> n) 67 { 68 memset(G, 0, sizeof(G)); 69 for (int i = 0; i < m; i++) 70 { 71 cin >> x >> y >> c; 72 G[x][y] += c; 73 } 74 int ans = 0; 75 int res = argument(); 76 while (res) 77 { 78 ans += res; 79 res = argument(); 80 } 81 cout << ans << endl; 82 } 83 return 0; 84 }
poj1273 Drainage Ditches
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。