首页 > 代码库 > 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;}