Thieves

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

11

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define MAXN 1010
#define MAXM 1000000
#define INF 0x3f3f3f3f
int dis[MAXN],vis[MAXN],map[MAXN][MAXN],cur[MAXN];
int n,S,H,m,cnt,head[MAXN];
struct node
{
	int u,v,cap,flow,next;
}edge[MAXM];
void add(int a,int b,int c)
{
	node E={a,b,c,0,head[a]};
	edge[cnt]=E;
	head[a]=cnt++;
	node E1={b,a,0,0,head[b]};
	edge[cnt]=E1;
	head[b]=cnt++;
}
void getmap()
{
	cnt=0;
	memset(head,-1,sizeof(head));
	scanf("%d%d%d%d",&n,&m,&S,&H);
	for(int i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		if(i==S||i==H)
		add(i,i+n,INF);
		else
		add(i,i+n,a);
	}
	for(int i=0;i<m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a+n,b,INF);
		add(b+n,a,INF);
	}
}
bool BFS(int s,int t)
{
	memset(dis,-1,sizeof(dis));
	memset(vis,0,sizeof(vis));
	queue<int>q;
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			node E=edge[i];
			if(!vis[E.v]&&E.cap>E.flow)
			{
				dis[E.v]=dis[E.u]+1;
				vis[E.v]=1;
				if(E.v==t) return true;
				q.push(E.v);
			}
		}
	}
	return false;
}
int DFS(int x,int a,int e)
{
	if(a==0||x==e) return a;
	int flow=0,f;
	for(int &i=cur[x];i!=-1;i=edge[i].next)
	{
		node &E=edge[i];
		if(dis[x]+1==dis[E.v]&&(f=DFS(E.v,min(E.cap-E.flow,a),e))>0)
		{
			a-=f;
			flow+=f;
			edge[i].flow+=f;
			edge[i^1].flow-=f;
			if(a==0) break;
		}
	}
	return flow;
}
int MAXflow(int s,int t)
{
	int flow=0;
	while(BFS(s,t))
	{
		memcpy(cur,head,sizeof(head));
		flow+=DFS(s,INF,t);
	}
	return flow;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		getmap();
		printf("%d\n",MAXflow(S,H+n));
	}
	return 0;
}

hdoj--3491--Thieves(最小割点集)

原文：http://blog.csdn.net/qq_29963431/article/details/51348199