Angry Programmer
You, a programmer of an important software house, have been fired because you didn't solve an important problem that was assigned to you. You are very furious and want to take revenge on your boss, breaking the communication between his computer and the central server.| Angry Programmer |
The computer of your boss and the central server are in the same network, which is composed of many machines (computers) and wires linking pairs of those machines. There is at most one wire between any pair of machines and there can be pairs of machines without a wire between them.
To accomplish your objective, you can destroy machines and wires, but you can't destroy neither the computer of your boss nor the central server, because those machines are monitored by security cameras. You have estimated the cost of blowing up each machine and the cost of cutting each wire in the network.
You want to determine the minimum cost of interrupting the communication between your boss' computer and the central server. Two computers A
i n - 1 Input
The input consists of several test cases. Each test case is represented as follows:- A line with two integers M
and W ( 2 , 0 ), representing (respectively) the number of machines and the number of wires in the network. - M - 2
lines, one per machine (different from the boss' machine and the central server), containing the following information separated by spaces: - An integer i
( 2 ) with the identifier of the machine. Assume that the boss' machine has id 1 and that the central server has id M . - An integer c
( 0 ) specifying the cost of destroying the machine.
- An integer i
- W
lines, one per wire, containing the following information separated by spaces: - Two integers j
and k ( 1 ) specifying the identifiers of the machines linked by the wire. Remember that the wire is bidirectional. - An integer d
( 0 ) specifying the cost of cutting the wire.
- Two integers j
The end of the input is specified by a line with the string ``0 0''.
Suppose that the machines have distinct identifiers.
Output
For each test case, print a line with the minimum cost of interrupting the communication between the computer of your boss and the central server.Sample Input
4 4 3 5 2 2 1 2 3 1 3 3 2 4 1 3 4 3 4 4 3 2 2 2 1 2 3 1 3 3 2 4 1 3 4 3 0 0
Sample Output
4 3
Colombia'2008 network flow + 拆點
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
#define INF int(1e9)
#define MAXN 120
#define MAXM 5000
using namespace std;
int N,M,e,RES;
int next[MAXM],v[MAXM],cap[MAXM],head[MAXN];
int dis[MAXN],p[MAXN],pe[MAXN],q[MAXN],work[MAXN],pf[MAXN];
void addedge(int a,int b,int K){
v[e]=b,next[e]=head[a],head[a]=e,cap[e]=K,e++;
v[e]=a,next[e]=head[b],head[b]=e,cap[e]=0,e++;
}
bool BFS(int s,int t){
int qf=0,qr,a,b,c;
memset(dis,-1,sizeof(dis));
q[qf++]=s,dis[s]=0;
for(qr=0;qr<qf;){
b=q[qr++];
if(DBG)printf("BFS %d(%d)\n",b/2,b);
for(a=head[b];a>=0;a=next[a]){
if(DBG)printf("b flow %d %d\n",v[a],cap[a]);
if(cap[a]&&dis[v[a]]<0){
dis[v[a]]=dis[b]+1;
if(DBG)printf("c %d dis %d\n",v[a]/2,dis[v[a]]);
if(v[a]==t)return 1;
q[qf++]=v[a];
}
}
}
return 0;
}
void dinic(){
int a,b,c,f,s=2,t=2*N;
while(BFS(s,t)){
memcpy(work,head,sizeof(work));
c=2,f=INF;
while(1){
if(DBG)printf("dinic %d\n",c);
for(a=work[c];a>=0;a=next[a]){
if(DBG)printf("a %d dis %d\n",v[a],dis[v[a]]);
if(cap[a]&&dis[v[a]]==dis[c]+1){b=v[a];break;}
}
if(a>=0)work[c]=next[a];else work[c]=-1;
if(a>=0){
if(b==t){
if(DBG)printf("reach t\n");
f=min(f,cap[a]);
RES+=f,p[b]=c,pe[b]=a;
for(b=t;b!=s;b=p[b])cap[pe[b]]-=f,cap[pe[b]^1]+=f;
c=2,f=INF;
}
else{
p[b]=c,pe[b]=a,pf[b]=f;
f=min(f,cap[a]);
c=b;
}
}
else{
if(c==2)break;
f=pf[c];
c=p[c];
}
}
}
}
void ans(){
RES=0,dinic();
printf("%d\n",RES);
}
int main(){
int a,b,c,zn[MAXN];
while(scanf("%d%d",&N,&M)==2){
if(N+M==0)break;
e=0,memset(head,-1,sizeof(head)),memset(zn,0,sizeof(zn));
rep(i,N-2){scanf("%d%d",&a,&b);
if(!b)zn[a]=1;
else addedge(2*a,2*a+1,b);}
rep(i,M){
scanf("%d%d%d",&a,&b,&c);
if(c&&!zn[a]&&!zn[b])addedge(2*a+1,2*b,c),addedge(2*b+1,2*a,c);}
addedge(2,3,INF);
ans();
}
}
and the crossings where the banks to be robbed are located, find out whether or not it is possible to plan a get-away route from every robbed bank to the city-bounds, without using a crossing more than once.
), followed by the number a of avenues ( 
), followed by the number b (
) of banks to be robbed.
and 
.
