有下界的最小流。
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();
}