What is the minimum cut problem in the game URAL1277 Cops and Thieves?

本文共计1047个文字，预计阅读时间需要5分钟。

《警察与盗贼描述：银河警察（Galaxpol）发现一个臭名昭著的盗贼团伙计划从地球行星博物馆偷走一件极为珍贵的展品——一台古老的微处理器。警察局长决定...》

Cops and Thieves

Description:

The Galaxy Police (Galaxpol) found out that a notorious gang of thieves has plans for stealing an extremely valuable exhibit from the Earth Planetary Museum— an ancient microprocessor. The police chiefs decided to intercept the criminals on the way from their refuge to the museum. A problem arose while planning the police operation: would it be possible for the Galaxpol staff to control all the possible routes of the criminals? The galaxy transport system is designed as follows. Each planet has a transport station that is connected to some of the other stations via two-way teleportation channels. Transport stations vary in their sizes, so different numbers of policemen may be required to take control over different stations. In order not to upset the operation, it was decided to leave the planets that are next to the museum or the refuge without any police control. Help the Galaxpol to place their staff at the stations in order to block all possible routes of the thieves. Input: The first line of the input contains a single integer 0 < K≤ 10000— the number of policemen engaged to control the stations. The second line has four integers: N, M, Sand Fdelimited with white-space character. Nis the number of stations in the galaxy (the stations are numbered from 1 to N); 2 < N≤ 100. Mis the number of teleportation channels; 1 < M≤ 10000. Sis the number of the planet (and the station) where the museum is; 1 ≤ S≤ N. Fis the number of the planet (and the station) where the thieves’ refuge is; 1 ≤ F≤ N. The next line contains Nintegers ( x ₁, …, x_N) separated with white-space character— the number of policemen required to control each of the stations (∑ _i=1 ^N x_i≤ 10000). Then Mlines follow that describe the teleportation channels. Each of these lines contains a pair of space-delimited integers— the numbers of stations being connected by a channel. The channel system is designed so that it is possible to reach any station from any other one (probably it would require several channel transitions). Output: Write “YES” if it is possible to block all the possible routes within given limitations, and “NO” otherwise. Sample Input:

10 5 5 1 5 1 6 6 11 1 1 2 1 3 2 4 3 4 4 5 Sample Output:

NO 题意： 给出一个无向图以及其起点和终点，每个点都有点权，问是否能用k个人去截断起点到终点的路径，注意不能将人员安排在起点和终点上面。 题解： 就是一个最小割的问题，建双向边以及拆点就好了。因为不能在起点和终点安排人员，所以起点和终点拆边的时候容量为无穷大就行了。 代码如下：

#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> #define INF 1e9 using namespace std; typedef long long ll; const int N = 505,M = 1e5+5; int n,m,s,F,tot,k; int w[N],head[N],d[N]; struct Edge{ int u,v,c,next; }e[M]; void adde(int u,int v,int c){ e[tot].v=v;e[tot].next=head[u];e[tot].c=c;head[u]=tot++; e[tot].v=u;e[tot].next=head[v];e[tot].c=0;head[v]=tot++; } int bfs(){ memset(d,0,sizeof(d));d[F]=1; queue <int > q;q.push(F); while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(e[i].c>0 && !d[v]){ d[v]=d[u]+1; q.push(v); } } } return d[s+n]!=0; } int dfs(int S,int a){ if(S==s+n || a==0) return a; int flow=0,f; for(int i=head[S];i!=-1;i=e[i].next){ int v=e[i].v; if(d[v]!=d[S]+1) continue ; f=dfs(v,min(a,e[i].c)); if(f>0){ e[i].c-=f; e[i^1].c+=f; flow+=f; a-=f; if(a==0) break; } } if(!flow) d[S]=-1; return flow; } int Dinic(int S,int T){ int flow = 0; while(bfs()) flow+=dfs(S,INF); return flow ; } int main(){ cin>>k>>n>>m>>s>>F; memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++){ if(i==s ||i==F) adde(i,i+n,INF); else adde(i,i+n,w[i]); } for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); adde(u+n,v,INF);adde(v+n,u,INF); } int flow = Dinic(F,s+n); if(flow>k) cout<<"NO"; else cout<<"YES"; return 0; }