首页 > 代码库 > POJ 1273(EK)
POJ 1273(EK)
题目大概意思是,有N条水沟和M个水池,问从第一个水池到最后一个水池在同一时间内能够流过多少水
第一行有两个整数N,M
接下来N行,每行有3个整数,a,b,c,代表从a到b能够流c单位的水
超级模板题,一个有向图,源点为1,汇点为M,套最大流模板就行了
我就通过这水题理解EK的...
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<queue> 5 #include<climits> 6 using namespace std; 7 #define N 210 8 #define clr(a,b) memset(a,b,sizeof(a)) 9 int cap[N][N];///容量 10 int n,m; 11 int a,b,c; 12 int EK(int s,int t)///s代表源点,t代表汇点 13 { 14 queue<int> q; 15 int flow[N][N];///流量 16 int low[N];///low[v]表示s-v的最小残量 17 int pre[N];///用于BFS寻找父亲节点 18 int u,v; 19 int maxflow = 0;///最大流 20 clr(flow,0);///初始时残量网络为0 21 while(1) 22 { 23 q.push(s);///把源点压入队列中 24 clr(low,0); 25 low[s] = INT_MAX; 26 while(!q.empty()) 27 { 28 u = q.front(); 29 q.pop(); 30 for(v = 0; v <= t; v ++) 31 { 32 if(!low[v] && cap[u][v] > flow[u][v])///找到新节点v 33 { 34 q.push(v); 35 low[v] = min(low[u], cap[u][v] - flow[u][v]); 36 pre[v] = u; 37 } 38 } 39 } 40 if(low[t] == 0) break;///找不到,则当前流已经是最大 41 for(u = t; u != s; u = pre[u]) 42 { 43 flow[pre[u]][u] += low[t]; 44 flow[u][pre[u]] -= low[t]; 45 } 46 maxflow += low[t]; 47 } 48 return maxflow; 49 } 50 int main() 51 { 52 int ans; 53 while(~scanf("%d%d",&n,&m)) 54 { 55 clr(cap,0); 56 57 for(int i=0; i<n; i++) 58 { 59 scanf("%d%d%d",&a,&b,&c); 60 cap[a][b] += c; 61 } 62 ans = EK(1,m); 63 printf("%d\n",ans); 64 } 65 return 0; 66 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。