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;

int d[MAXV];

int q[MAXV];

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

{

}

bool relabel()

{

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

{

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;

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;

{

total=0;

top=pool;

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);

total+=c;

}

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 main()

{