HDOJ 3157 Crazy Circuits
給一些電路上的兩個點和這兩個點之間最少要通過的電流，要求正極到負極間的流量再滿足條件的情況下最少
有源匯點上下界最小流:
建圖：
設原源匯點 s，t 建立超級源匯點S，T先不連接 t-->s 像無源匯點可行流判斷一樣的建圖，對S，T跑一遍最大流，記錄流量f1。。。 連接源匯點 t--->s 無下界，上界INF ....再對S，T跑一遍最大流，得到流量f2。。。
如果 
則存在最小流，最小流流量既 t--->s 的後悔邊的流量。
否則無解<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8aDE+CkNyYXp5IENpcmN1aXRzPC9oMT4KPHN0cm9uZz5UaW1lIExpbWl0OiA0MDAwLzIwMDAgTVMgKEphdmEvT3RoZXJzKSAgICBNZW1vcnkgTGltaXQ6IDMyNzY4LzMyNzY4IEsgKEphdmEvT3RoZXJzKTxicj4KVG90YWwgU3VibWlzc2lvbihzKTogNTIwICAgIEFjY2VwdGVkIFN1Ym1pc3Npb24ocyk6IDI2Mjxicj4KPC9zdHJvbmc+PGJyPgo8YnI+CgpQcm9ibGVtIERlc2NyaXB0aW9uCgpZb3Whr3ZlIGp1c3QgYnVpbHQgYSBjaXJjdWl0IGJvYXJkIGZvciB5b3VyIG5ldyByb2JvdCwgYW5kIG5vdyB5b3UgbmVlZCB0byBwb3dlciBpdC4gWW91ciByb2JvdCBjaXJjdWl0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIGVsZWN0cmljYWwgY29tcG9uZW50cyB0aGF0IGVhY2ggcmVxdWlyZSBhIGNlcnRhaW4gYW1vdW50IG9mIGN1cnJlbnQgdG8gb3BlcmF0ZS4gRXZlcnkgY29tcG9uZW50IGhhcyBhICYjNDM7IGFuZCBhIC0gbGVhZCwgd2hpY2ggYXJlIGNvbm5lY3RlZAogb24gdGhlIGNpcmN1aXQgYm9hcmQgYXQganVuY3Rpb25zLiBDdXJyZW50IGZsb3dzIHRocm91Z2ggdGhlIGNvbXBvbmVudCBmcm9tICYjNDM7IHRvIC0gKGJ1dCBub3RlIHRoYXQgYSBjb21wb25lbnQgZG9lcyBub3Qg"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).
Figure 1: Examples of two valid circuit diagrams.
In (a), all components can be powered along directed paths from the positive terminal to the negative terminal.
In (b), components 4 and 6 cannot be powered, since there is no directed path from junction 4 to the negative terminal.
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?
Hint
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.
Input
The input file will contain multiple test cases. Each test case begins with a single line containing two integers:
N (0 <=
N <= 50), the number of junctions not including the positive and negative terminals, and
M (1
<=
M <= 200), the number of components in the circuit diagram. The next
M lines each contain a description of some component in the diagram. The
ith component description contains three fields:
pi,
the positive junction to which the component is connected,
ni, the negative junction to which the component is connected, and an integer
Ii (1 <=
Ii <= 100), the minimum amount
of current required for component
i to function. The junctions
pi and
niare specified as either the character "+' indicating the positive terminal, the character '-' indicating the negative
terminal, or an integer (between 1 and
N) indicating one of the numbered junctions. No two components have the same positive junction and the same negative junction. The end-of-file is denoted by an invalid test case with
N =
M =
0 and should not be processed.
Output
For each input test case, your program should print out either a single integer indicating the minimum amount of current that must be supplied at the positive terminal in order to ensure that every component is powered, or the message "
impossible"
if there is no way to direct a sufficient amount of current to each component simultaneously.
Sample Input
6 10
+ 1 1
1 2 1
1 3 2
2 4 5
+ - 1
4 3 2
3 5 5
4 6 2
5 - 1
6 5 3
4 6
+ 1 8
1 2 4
1 3 5
2 4 6
3 - 1
3 4 3
0 0
Sample Output
9
impossible
Source
2008 ACM-ICPC Pacific Northwest Region
#include
#include
#include
#include
using namespace std;
const int maxn=50500;
const int maxm=1010000;
const int INF=0x3f3f3f3f;
struct Edge
{
int to,next,cap,flow;
}edge[maxm];
int Size,Adj[maxn];
int gap[maxn],dep[maxn],pre[maxn],cur[maxn];
void init()
{
Size=0; memset(Adj,-1,sizeof(Adj));
}
void addedge(int u,int v,int w,int rw=0)
{
edge[Size].to=v; edge[Size].cap=w; edge[Size].next=Adj[u];
edge[Size].flow=0; Adj[u]=Size++;
edge[Size].to=u; edge[Size].cap=rw; edge[Size].next=Adj[v];
edge[Size].flow=0; Adj[v]=Size++;
}
int sap(int start,int end,int N)
{
memset(gap,0,sizeof(gap));
memset(dep,0,sizeof(dep));
memcpy(cur,Adj,sizeof(Adj));
int u=start;
pre[u]=-1; gap[0]=N;
int ans=0;
while(dep[start]edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
for(int i=pre[u];~i;i=pre[edge[i^1].to])
{
edge[i].flow+=Min;
edge[i^1].flow-=Min;
}
u=start;
ans+=Min;
continue;
}
bool flag=false;
int v;
for(int i=cur[u];~i;i=edge[i].next)
{
v=edge[i].to;
if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u])
{
flag=true;
cur[u]=pre[v]=i;
break;
}
}
if(flag)
{
u=v;
continue;
}
int Min=N;
for(int i=Adj[u];~i;i=edge[i].next)
{
if(edge[i].cap-edge[i].flow&&dep[edge[i].to]='0'&&ch<='9'))
{
if(ch=='+') return 0;
else if(ch=='-') return n+1;
else
{
ok=true;
ret=ret*10+(ch-'0');
}
}
else if(ok==true)
{
break;
}
}
return ret;
}
int in[maxn];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0) break;
init(); memset(in,0,sizeof(in));
for(int i=0;i0)
{
sum+=in[i];
addedge(n+2,i,in[i]);
}
if(in[i]<0) addedge(i,n+3,-in[i]);
}
int MaxFlow1=sap(n+2,n+3,n+4);
addedge(n+1,0,INF);
int MaxFlow2=sap(n+2,n+3,n+4);
if(MaxFlow1+MaxFlow2==sum)
{
printf("%d\n",edge[Size-2].flow);
}
else puts("impossible");
}
return 0;
}
