HDU3157[Crazy Circuits]

有下界的最小流。


CODE:


/*


AUTHOR: Su Jiao


DATE: 2010-7-20


DESCRIPTION:


网络流 乱做


http://acm.hdu.edu.cn/showproblem.php?pid=3157


*/


#include <stdio.h>


#include <string.h>


 


const int oo=(~0u)>>1;


const int MAXV=1102;


const int MAXE=6200;


typedef struct struct_edge* edge;


struct struct_edge{int v,c;edge n,b;};


struct_edge pool[MAXE];


edge top;


int S,T,V;


edge adj[MAXV];


int d[MAXV];


int q[MAXV];


int head,tail;


void add_edge(int u,int v,int c)


{


     top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;


     top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;


     adj[u]->b=adj[v],adj[v]->b=adj[u];


}


bool relabel()


{


     for (int i=0;i<V;d[i++]=oo) ;


     d[q[head=tail=0]=T]=0;


     while (head<=tail)


     {


           int u=q[head++];


           for (edge i=adj[u];i;i=i->n)


               if (i->b->c&&d[i->v]==oo)


                  d[q[++tail]=i->v]=d[u]+1;


           if (d[S]!=oo) return true;


     }


     return false;


}


int augment(int u,int e)


{


    if (u==T) return e;


    int f=0;


    for (edge i=adj[u];i&&e;i=i->n)


        if (i->c&&d[u]==d[i->v]+1)


           if (int df=augment(i->v,e<i->c?e:i->c))


              i->c-=df,i->b->c+=df,e-=df,f+=df;


    return f;


}


int dinic()


{


    int f=0;


    while (relabel()) f+=augment(S,oo);


    return f;


}


 


int N,M;


int ss,tt;


int total;


edge tt_to_ss;


bool read()


{


     total=0;


     top=pool;


     memset(adj,0,sizeof(adj));


     scanf(“%d%d”,&N,&M);


     if (N==0&&M==0) return false;


     ss=0,tt=N+1;


     S=N+2,T=N+3,V=N+4;


     for (int i=0;i<M;i++)


     {


         static const int MAXLENGTH=1024;


         char s[MAXLENGTH];


         int a,b,c;


         scanf(“%s”,&s);


         if (sscanf(s,“%d”,&a)==EOF)


            if (*s==’+’) a=ss;


            else if (*s==’-‘)  a=tt;


         scanf(“%s”,&s);


         if (sscanf(s,“%d”,&b)==EOF)


            if (*s==’+’) b=ss;


            else if (*s==’-‘) b=tt;


         scanf(“%d”,&c);


         add_edge(a,b,oo);


         add_edge(S,b,c);


         add_edge(a,T,c);


         total+=c;


     }


     add_edge(tt,ss,oo);


     tt_to_ss=top-2;


     return true;


}


void write()


{


     total-=dinic();


     if (total) printf(“impossible\n”);


     else


     {


         S=N+1,T=0,V-=2;


         int answer=tt_to_ss->b->c-dinic();


         printf(“%d\n”,answer);


     }


}


 


int main()


{


    while (read()) write();


}