ThievesTime Limit: 3000/1000 MS (Java/Others)Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1453Accepted Submission(s): 651
Problem Description
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?
Input
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.
Output
For each test case, output a single integer in a separate line, indicating the minimum number of people the police used.
Sample Input
15 5 1 51 6 6 11 11 21 32 43 44 5
Sample Output
11
Source
2010 ACM-ICPC Multi-University Training Contest（6）——Host by BIT
Recommend
zhouzeyong|We have carefully selected several similar problems for you:33761068238934882063
题意：n个点m条边的无向图，告诉起点S和终点H，现在知道起点有小偷要去H偷东西，为了抓获小偷告诉每个点要安排的警察数量，现在问在哪些点安排警察可以使警察数量最少，求出最小数量。
思路： 关键要理解最小割的建图思想，因为点上有权值，所以拆点，i->i+n建边，容量为点上权值，这样就能保证这个点可能被选择，然后点与点之间的边建图时容量为INF，保证它不被割到（因为我们要选的只是点上的权值），然后起点S->S+n,终点H->H+n建边容量为INF，起点和终点不能方放警察。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;#define INF 0x3f3f3f3f#define mod 1000000009const int maxn = 1005;const int MAXN = 2005;const int MAXM = 200000;const int N = 1005;int S,H,n,m;struct Edge{int to,next,cap,flow;}edge[MAXM];int tol;int head[MAXN];int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];void init(){tol=0;memset(head,-1,sizeof(head));}//加边，，单向图三个参数，双向图四个参数void addedge(int u,int v,int w,int rw=0){edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u];edge[tol].flow=0; head[u]=tol++;edge[tol].to=u; edge[tol].cap=rw; edge[tol].next=head[v];edge[tol].flow=0; head[v]=tol++;}//输入参数：起点，终点，点的总数//点的编号没有影响，只要输入点的总数int sap(int start,int end,int N){memset(gap,0,sizeof(gap));memset(dep,0,sizeof(dep));memcpy(cur,head,sizeof(head));int u=start;pre[u]=-1;gap[0]=N;int ans=0;while (dep[start]<N){if (u==end){int Min=INF;for (int i=pre[u];i!=-1;i=pre[edge[i^1].to])if (Min>edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;for (int i=pre[u];i!=-1;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!=-1;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=head[u];i!=-1;i=edge[i].next)if (edge[i].cap-edge[i].flow && dep[edge[i].to]<Min){Min=dep[edge[i].to];cur[u]=i;}gap[dep[u]]–;if (!gap[dep[u]]) return ans;dep[u]=Min+1;gap[dep[u]]++;if (u!=start) u=edge[pre[u]^1].to;}return ans;}int main(){#ifndef ONLINE_JUDGEfreopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);#endifint i,j,t,x,y;sf(t);while (t–){scanf("%d%d%d%d",&n,&m,&S,&H);init();for (i=1;i<=n;i++){scanf("%d",&x);if (i==S||i==H) continue;addedge(i,i+n,x);}addedge(S,S+n,INF);addedge(H,H+n,INF);addedge(0,S,INF);addedge(H+n,2*n+1,INF);for (i=0;i<m;i++){scanf("%d%d",&x,&y);addedge(x+n,y,INF);addedge(y+n,x,INF);}printf("%d\n",sap(0,2*n+1,2*n+2));}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
一个人的期望值越大，心理承受力就会越小，就越经受不住失败的打击，
