首页 > 代码库 > POJ 1459(EK)
POJ 1459(EK)
这题是学着小媛学姐写的..
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<queue> 5 #include <climits> 6 using namespace std; 7 #define N 120 8 9 int n, np, nc, m; 10 int cap[N][N]; 11 int EK(int s, int t) 12 { 13 queue<int> q; 14 int flow[N][N]; 15 int low[N]; 16 int u,v,maxflow=0; 17 int pre[N]; 18 memset(flow,0,sizeof(flow)); 19 while(1) 20 { 21 q.push(s); 22 memset(low,0,sizeof(low)); 23 low[s] = INT_MAX; 24 while(!q.empty()) 25 { 26 u = q.front(); 27 q.pop(); 28 for(v = 0; v <= t; v ++) 29 { 30 if(!low[v] && cap[u][v] > flow[u][v]) 31 { 32 q.push(v); 33 low[v] = min(low[u], cap[u][v] - flow[u][v]); 34 pre[v] = u; 35 } 36 } 37 } 38 if(low[t] == 0) break; 39 for(u = t; u != s; u = pre[u]) 40 { 41 flow[pre[u]][u] += low[t]; 42 flow[u][pre[u]] -= low[t]; 43 } 44 maxflow += low[t]; 45 } 46 return maxflow; 47 } 48 int main() 49 { 50 char ch; 51 int from, to, len, ans; 52 while(~scanf("%d%d%d%d",&n,&np,&nc,&m)) 53 { 54 memset(cap, 0, sizeof(cap)); 55 while(m--) 56 { 57 scanf(" (%d,%d)%d", &from, &to, &len); 58 cap[from][to] = len; 59 } 60 while(np--) 61 { 62 scanf(" (%d)%d",&from, &len); 63 cap[n+1][from] = len; 64 } 65 while(nc--) 66 { 67 scanf(" (%d)%d",&from, &len); 68 cap[from][n+2] = len; 69 } 70 ans = EK(n+1, n+2); 71 printf("%d\n",ans); 72 } 73 return 0; 74 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。