首页 > 代码库 > hdu 1532 Drainage Ditches(最大流)
hdu 1532 Drainage Ditches(最大流)
题目:
链接:点击打开链接
题意:
求最大流速。
思路:
Edmond_karp就行。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; #define INF 100000000 const int N = 220; int cap[N][N],flow[N][N]; int a[N]; int n,m; int s,e,c; void edmonds_karp(int s,int t) { queue<int> q; memset(flow,0,sizeof(flow)); int f = 0; int p[N]; for(;;) { memset(a,0,sizeof(a)); a[s] = INF; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int v=1; v<=n; v++) { if(!a[v] && cap[u][v] > flow[u][v]) { p[v] = u; q.push(v); a[v] = a[u] < cap[u][v] - flow[u][v] ? a[u] : cap[u][v] - flow[u][v]; } } } if(a[t] == 0) break; for(int u=t; u!=s; u=p[u]) { flow[p[u]][u] += a[t]; flow[u][p[u]] += a[t]; } f += a[t]; } printf("%d\n",f); } int main() { //freopen("input.txt","r",stdin); while(scanf("%d%d",&n,&m) != EOF) { memset(cap,0,sizeof(cap)); for(int i=0; i<n; i++) { scanf("%d%d%d",&s,&e,&c); cap[s][e] += c; } edmonds_karp(1,m); } return 0; }--------------------------------------------------------------------------------
收获:
------>增广路算法,Edmond_karp模板:
queue<int> q; memset(flow,0,sizeof(flow)); int f = 0; int p[N]; for(;;) { memset(a,0,sizeof(a)); a[s] = INF; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int v=1; v<=n; v++) { if(!a[v] && cap[u][v] > flow[u][v]) { p[v] = u; q.push(v); a[v] = a[u] < cap[u][v] - flow[u][v] ? a[u] : cap[u][v] - flow[u][v]; } } } if(a[t] == 0) break; for(int u=t; u!=s; u=p[u]) { flow[p[u]][u] += a[t]; flow[u][p[u]] += a[t]; } f += a[t]; }
------------------------------------------------------------------
战斗,从不退缩;奋斗,永不停歇~~~~~~~~~~~~~
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。