首页 > 代码库 > poj1459最大流
poj1459最大流
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int n,p,c,m;const int maxn=1111;int Map[maxn][maxn];int s;int e;int level[maxn];const int INF=0xfffffff;int Min(int a,int b){ return a>b?b:a;}int bfs(){ memset(level,0,sizeof(level)); queue<int > q; q.push(s); level[s]=1; while(!q.empty()){ int cur=q.front() ;q.pop(); for(int i=0;i<n+2;i++){ if(Map[cur][i]&&!level[i]){ level[i]=level[cur]+1; q.push(i); } } } return level[e];}int dfs(int x,int val){ int tem=val; if(x==e) return val; for(int i=0;i<n+2&&tem;i++){ if(Map[x][i]&&level[i]==level[x]+1){ int t=dfs(i,Min(tem,Map[x][i])); Map[x][i]-=t;Map[i][x]+=t; tem-=t; } } return val-tem;}int dinic(){ int t;int ans=0; while(bfs()){ while(t=dfs(s,INF)){ ans+=t; } } return ans;}int main(){ char str[1000]; while(scanf("%d%d%d%d",&n,&p,&c,&m)!=EOF){ s=n;e=n+1; for(int i=0;i<n+2;i++) for(int j=0;j<n+2;j++) Map[i][j]=0; for(int i=0;i<m;i++){ int a;int b;int d; while(getchar()!=‘(‘); scanf("%d,%d)%d",&a,&b,&d); Map[a][b]=d; } for(int i=0;i<p;i++){ int a;int b; while(getchar()!=‘(‘); scanf("%d)%d",&a,&b); Map[s][a]=b; } for(int i=0;i<c;i++){ int a;int b; while(getchar()!=‘(‘) ; scanf("%d)%d",&a,&b); Map[a][e]=b; } printf("%d\n",dinic()); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。