Crazy Circuits
This problem will be judged on HDU. Original ID: 3157
64-bit integer IO format: %I64d Java class name: Main
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?
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
Output
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
- 构造附加网络，不添加[T,S]边
- 对[SS,TT]求最大流
- 添加[T,S]边
- 对[SS,TT]求最大流，若满流，则边[T,S]上的流量即是最小流
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = ;
struct arc {
int to,flow,next;
arc(int x = ,int y = ,int z = -) {
to = x;
flow = y;
next = z;
}
} e[maxn*maxn];
int head[maxn],cur[maxn],d[maxn],du[maxn],tot;
void add(int u,int v,int flow) {
e[tot] = arc(v,flow,head[u]);
head[u] = tot++;
e[tot] = arc(u,,head[v]);
head[v] = tot++;
}
bool bfs(int S,int T) {
queue<int>q;
q.push(S);
memset(d,-,sizeof d);
d[S] = ;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; ~i; i = e[i].next) {
if(e[i].flow && d[e[i].to] == -) {
d[e[i].to] = d[u] + ;
q.push(e[i].to);
}
}
}
return d[T] > -;
}
int dfs(int u,int T,int low) {
if(u == T) return low;
int a,tmp = ;
for(int &i = cur[u]; ~i; i = e[i].next) {
if(e[i].flow && d[e[i].to] == d[u]+&&(a=dfs(e[i].to,T,min(e[i].flow,low)))) {
e[i].flow -= a;
e[i^].flow += a;
low -= a;
tmp += a;
if(!low) break;
}
}
if(!tmp) d[u] = -;
return tmp;
}
int Dinic(int S,int T,int ret = ) {
while(bfs(S,T)) {
memcpy(cur,head,sizeof head);
ret += dfs(S,T,INF);
}
return ret;
}
int main() {
char a[],b[];
int n,m,u,v,bound,S,T,SS,TT;
while(scanf("%d%d",&n,&m),n||m) {
memset(head,-,sizeof head);
memset(du,,sizeof du);
int sum = S = ;
T = n + ;
SS = T + ;
TT = SS + ;
for(int i = tot = ; i < m; ++i) {
scanf("%s%s%d",a,b,&bound);
if(a[] == '+') u = S;
else sscanf(a,"%d",&u);
if(b[] == '-') v = T;
else sscanf(b,"%d",&v);
add(u,v,INF);
du[u] -= bound;
du[v] += bound;
}
for(int i = ; i <= T; ++i) {
if(du[i] > ) {
add(SS,i,du[i]);
sum += du[i];
} else add(i,TT,-du[i]);
}
u = Dinic(SS,TT);
add(T,S,INF);
v = Dinic(SS,TT);
if(u + v == sum) printf("%d\n",e[tot-].flow);
else puts("impossible");
}
return ;
}