题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3157
You’ve just built a circuit board for your new robot, and now you need to power it. Your robot circuit consists of a number of electrical components that each require a certain amount of current to operate. Every component has a + and a - lead, which are connected on the circuit board at junctions. Current flows through the component from + to - (but note that a component does not "use up" the current: everything that comes in through the + end goes out the - end).
The junctions on the board are labeled 1, ..., N, except for
two special junctions labeled + and - where the power supply terminals are
connected. The + terminal only connects + leads, and the - terminal only
connects - leads. All current that enters a junction from the - leads of
connected components exits through connected + leads, but you are able to
control how much current flows to each connected + lead at every junction
(though methods for doing so are beyond the scope of this problem1).
Moreover, you know you have assembled the circuit in such a way that there are
no feedback loops (components chained in a manner that allows current to flow in
a loop).
In the interest of saving power, and also to ensure that your circuit does not overheat, you would like to use as little current as possible to get your robot to work. What is the smallest amount of current that you need to put through the + terminal (which you can imagine all necessarily leaving through the - terminal) so that every component on your robot receives its required supply of current to function?
1 For
those who are electronics-inclined, imagine that you have the ability to adjust
the potential on any componentwithout altering its current requirement, or
equivalently that there is an accurate variable potentiometer connected in
series with each component that you can adjust. Your power supply will have
ample potential for the circuit.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int maxn=;
const int M = +; struct Edge
{
int to,cap,next;
}edge[M*];
int head[maxn],edgenum;
int n,m,from,to,vnum,s,t; void add(int u,int v,int cap)
{
edge[edgenum].to=v;
edge[edgenum].cap=cap;
edge[edgenum].next=head[u];
head[u]=edgenum++; edge[edgenum].to=u;
edge[edgenum].cap=;
edge[edgenum].next=head[v];
head[v]=edgenum++;
} int level[maxn];
int gap[maxn];
void bfs(int to)
{
memset(level,-,sizeof(level));
memset(gap,,sizeof(gap));
level[to]=;
gap[level[to] ]++;
queue<int> Q;
Q.push(to);
while (!Q.empty())
{
int u=Q.front() ;Q.pop() ;
for (int i=head[u] ;i!=- ;i=edge[i].next)
{
int v=edge[i].to;
if (level[v] != -) continue;
level[v]=level[u]+;
gap[level[v] ]++;
Q.push(v);
}
}
} int cur[maxn];
int pre[maxn];
int SAP(int from,int to)
{
bfs(to);
memset(pre,-,sizeof(pre));
memcpy(cur,head,sizeof(head));
int u=pre[from]=from,flow=,aug=inf;
gap[from]=vnum;
while (level[from]<vnum)
{
bool flag=false;
for (int &i=cur[u] ;i!=- ;i=edge[i].next)
{
int v=edge[i].to;
if (edge[i].cap && level[u]==level[v]+)
{
flag=true;
aug=min(aug,edge[i].cap);
pre[v]=u;
u=v;
if (v==to)
{
flow += aug;
for (u=pre[u] ;v!=from ;v=u ,u=pre[u])
{
edge[cur[u] ].cap -= aug;
edge[cur[u]^ ].cap += aug;
}
aug=inf;
}
break;
}
}
if (flag) continue;
int minlevel=vnum;
for (int i=head[u] ;i!=- ;i=edge[i].next)
{
int v=edge[i].to;
if (edge[i].cap && level[v]<minlevel)
{
minlevel=level[v];
cur[u]=i;
}
}
if (--gap[level[u] ]==) break;
level[u]=minlevel+;
gap[level[u] ]++;
u=pre[u];
}
return flow;
} int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
if (!n && !m) break;
memset(head,-,sizeof(head));
edgenum=;
char c[],c2[];
int u,v;
int cap,f=M;
s= ;t=n+ ;from=t+ ;to=from+ ;
vnum=to+;
int sum=;
for (int i= ;i<m ;i++)
{
scanf("%s%s%d",&c,&c2,&cap);
sum += cap;
if (c[]=='+') u=s;
else sscanf(c,"%d",&u);
if (c2[]=='-') v=t;
else sscanf(c2,"%d",&v);
add(u,v,f-cap);
add(from,v,cap);
add(u,to,cap);
//cout<<"debug"<<endl;
}
int Maxflow=SAP(from,to);
int d=edgenum;
add(t,s,inf);
Maxflow += SAP(from,to);
int flag=;
for (int i=head[from] ;i!=- ;i=edge[i].next)
{
if (edge[i].cap) {flag=;break; }
}
if (Maxflow==sum) printf("%d\n",edge[(d^)].cap);
else printf("impossible\n");
}
return ;
}