sgu 176 有源汇有上下界的最小流模板题

/*参考博文:http://hi.baidu.com/dragon_eric123/item/82e259200ece744046996282

  有上下界的有源最小流

*/

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace  std;

#define N 300

#define inf 0x3fffffff

struct node {

int u,v,w,f,next;

}bian[N*N*2];

int head[N],yong,dis[N],work[N];

void init(){

yong=0;

memset(head,-1,sizeof(head));

}

void addbian(int u,int v,int w,int f) {

bian[yong].u=u;

bian[yong].v=v;

bian[yong].w=w;

bian[yong].f=f;

bian[yong].next=head[u];

head[u]=yong++;

}

void add(int u,int v,int w,int f) {

addbian(u,v,w,f);

addbian(v,u,0,f);

}

int min(int a,int b)

{

    return a<b?a:b;

}

int bfs(int s,int t)

{

    memset(dis,-1,sizeof(dis));

    queue<int>q;

    q.push(s);

    dis[s]=0;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-1;i=bian[i].next)

        {

            int v=bian[i].v;

            if(bian[i].w&&dis[v]==-1)

            {

                dis[v]=dis[u]+1;

                q.push(v);

                if(v==t)

                    return 1;

            }

        }

    }

    return 0;

}

int dfs(int  s,int limit,int t)

{

    if(s==t)return limit;

    for(int &i=work[s];i!=-1;i=bian[i].next)

    {

        int v=bian[i].v;

        if(bian[i].w&&dis[v]==dis[s]+1)

        {

            int tt=dfs(v,min(limit,bian[i].w),t);

            if(tt)

            {

                bian[i].w-=tt;

                bian[i^1].w+=tt;

                return tt;

            }

        }

    }

    return 0;

}

int dinic(int s,int t)

{

    int ans=0;

    while(bfs(s,t))

    {

        memcpy(work,head,sizeof(head));

        while(int tt=dfs(s,inf,t))

            ans+=tt;

    }

    return ans;

}

int main() {

   int n,m,i,a,b,c,d,w[N],sum,f,ff,index,s,t;

   while(scanf("%d%d",&n,&m)!=EOF) {

    init();

    s=0;t=n+1;sum=0;

    memset(w,0,sizeof(w));

   for(i=0;i<m;i++) {

        scanf("%d%d%d%d",&a,&b,&c,&d);

          if(d){

          add(a,b,0,c);

          w[a]-=c;

          w[b]+=c;

          }

          else

            add(a,b,c,c);

    }

    for(i=1;i<=n;i++) {

        if(w[i]>0) {

            sum+=w[i];

            add(s,i,w[i],0);

        }

        else add(i,t,-w[i],0);

    }

    f=dinic(s,t);

    index=yong;

    add(n,1,inf,0);

    ff=dinic(s,t);

    if(f+ff!=sum)

        printf("Impossible\n");

    else {

        printf("%d\n",bian[index^1].w);

        for(i=0;i<m-1;i++)

            printf("%d ",bian[i*2].f-bian[i*2].w);

        printf("%d\n",bian[i*2].f-bian[i*2].w);

    }

   }

return 0;

}
巴特西

sgu 176 有源汇有上下界的最小流模板题

最新文章

热门文章
