首页 > ACM题库 > HDU-杭电 > HDU 3491-Thieves[解题报告]HOJ
2014
04-04

HDU 3491-Thieves[解题报告]HOJ

Thieves

问题描述 :

In the kingdom of Henryy, there are N (2 <= N <= 100) cities, with M (M <= 10000) two-direct ways connecting them.
A group of thieves from abroad plan to steal the metropolitan museum in city H (It has not been demolished). However, the brave, brilliant, bright police in the kingdom have known this plan long before, and they also plan to catch the thieves. The thieves are in the city S at present. The police try to catch them on their way from S to H. Although the thieves might travel this way by more than one group, our excellent police has already gather the statistics that the number of the people needed in city I (1<=I<=N) to arrest the thieves.
The police do not want to encounter the thieves in either city S or city H.
The police finish the task with the minimum number of people. Do you know the exact number?

输入:

The first line contains an integer T (T <= 10), indicating the number of the test cases.
The first line of each test case has four integers: N, the number of the cities; M, the number of the roads; S (1<=S<=N), the label of city S; H (1<=T<=N, S≠H), the label of city H.
The second line contains N integers, indicating the number of people needed in each city. The sum of these N integers is less than 10000.
Then M lines followed, each containing two integers x and y, indicating that there is a two-direct roads between city x and y. Notices that no road between city S and H.
A blank line is followed after each test case.

输出:

The first line contains an integer T (T <= 10), indicating the number of the test cases.
The first line of each test case has four integers: N, the number of the cities; M, the number of the roads; S (1<=S<=N), the label of city S; H (1<=T<=N, S≠H), the label of city H.
The second line contains N integers, indicating the number of people needed in each city. The sum of these N integers is less than 10000.
Then M lines followed, each containing two integers x and y, indicating that there is a two-direct roads between city x and y. Notices that no road between city S and H.
A blank line is followed after each test case.

样例输入:

1
5 5 1 5
1 6 6 11 1
1 2
1 3
2 4
3 4
4 5

样例输出:

11


题意:有n个城市,每个城市有一定数量的警察,有一群小偷,从城市S,到T,问最少需要多少警察可以使小偷到不了T城市。

将每个城市的警察数量看成流量,那么问题就转化成求S – T的最小割。

将每个点拆成i , i + n ,流量是该点的值.然后跑一次最大流就可以了。

最大流最小割定理:任意一个流网络的最大流量等于该网络的最小的割的容量。

#include<stdio.h>
#include<string.h>
#define INF 100000000
int map[210][210],pre[210],weight[210];
int n,m,start,end;
int bfs(){
	int h=0,t=1,q[40100];
	q[h]=start;
	memset(pre,0,sizeof(pre));
	while(h<t){
		int cur=q[h];
		for(int i=1;i<=2*n;i++){
			if(pre[i]==0&&map[cur][i]>0){
				q[t++]=i;
				pre[i]=cur;
				if(i==end)	return 1;		
			}
		}
		h++;
	}
	return 0;
}
int query(){
	int min=2*INF,u=end,v;
	while(u!=start){
		v=pre[u];
		if(min>map[v][u])	min=map[v][u];
		u=v;
	}
	return min;
}
void update(int min){
	int u,v;
	u=end;
	while(u!=start){
		v=pre[u];
		map[v][u]-=min;
		map[u][v]+=min;
		u=v;
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d%d",&n,&m,&start,&end);
		memset(map,0,sizeof(map));
		for(int i=1;i<=n;i++){
			scanf("%d",&weight[i]);
			map[i*2-1][i*2]=weight[i];
		}
		map[start*2-1][start*2]=map[end*2-1][end*2]=0;
		start*=2;
		end=end*2-1;
		while(m--){
			int x,y;
			scanf("%d%d",&x,&y);
			map[y*2][x*2-1]=map[x*2][y*2-1]=INF;
		}
		int ans=0;
		while(bfs()){
			int min=query();
			ans+=min;
			update(min);
		}
		printf("%d\n",ans);
	}
	return 0;
}