HDU - 4289 Control （最小割+建圖+拆點）

連結：https://cn.vjudge.net/problem/HDU-4289

題意：多組樣例。每組樣例第一行給出n和m（n個城市，m條路相連）。接下來一行給出s（源點）和t（彙點）。接下來一行n個數，代表每個城市的花費。接下來m行描述圖，u、v代表兩個城市有路。一群不法分子會打算從s出發到目的地t。求用最小的花費，選出一個點集（即若幹個城市），使得所有不法分子不能到達t。假如選擇了點i（即城市i），那麼經過城市i的所有不法分子都會被攔住。

思路：這打眼一看，就知道是一個網絡流的題。問題是怎麼用網絡流解決它。因為求最小值，不難想到最小割。那麼，難題就是怎麼建圖，使得求出的最小割就是最小花費。最小割就是把一些邊割掉後，無法從源點到達彙點，這和題目要求一模一樣啊。問題是，題目中的邊沒有邊權，有點權，那麼很容易想到要拆點。怎麼拆呢？把每個點拆成兩個點（假設為i，拆成i和i+n），點i到新添的虛點n+i的容量為點i的權值。至于給出的邊（假設為u和v之間的邊），把它也拆成兩條邊，因為是雙向邊，虛點n+u到點v的的容量為點u的權值，虛點n+v到點u的的容量為點v的權值。記得都加上反向弧，跑一遍Dinic求從s到n+t的最大流即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 410;
const int M = 1e5+10;
const int inf = 0x3f3f3f3f;
struct node
{
	int to,ca,next;
}g[M];
int n,m,s,t,cnt,head[N],cur[N],deep[N],w[N];
void Init()
{
	cnt=0;
	memset(head,-1,sizeof(head));
	return ;
}
void add(int u,int v,int w)
{
	g[cnt].to=v;
	g[cnt].ca=w;
	g[cnt].next=head[u];
	head[u]=cnt++;
	return ;
}
bool bfs()
{
	memset(deep,0,sizeof(deep));
	queue<int> q;
	int u,v;
	deep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		if(u==t) return 1;
		for(int i=head[u];i!=-1;i=g[i].next)
		{
			v=g[i].to;
			if(g[i].ca>0&&!deep[v])
			{
				deep[v]=deep[u]+1;
				q.push(v);	
			}	
		}	
	}	
	return deep[t]!=0;
}
ll dfs(int u,int flow)
{
	if(u==t||!flow) return flow;
	ll ans=0,nowflow;
	int v;
	for(int& i=cur[u];i!=-1;i=g[i].next)
	{
		v=g[i].to;
		if(g[i].ca>0&&deep[v]==deep[u]+1)
		{
			nowflow=dfs(v,min(flow,g[i].ca));
			if(nowflow)
			{
				flow-=nowflow;
				ans+=nowflow;
				g[i].ca-=nowflow;
				g[i^1].ca+=nowflow;
				if(!flow) break;
			}
		}
	}
	if(!ans) deep[u]=0;
	return ans;
}
ll Dinic()
{
	ll maxflow=0;
	ll flow;
	while(bfs())
	{
		memcpy(cur,head,sizeof(head));
		while(flow=dfs(s,inf))
			maxflow+=flow;
	}
	return maxflow;
}
int main(void)
{
	int u,v;
	while(~scanf("%d%d",&n,&m))
	{
		Init();
		scanf("%d%d",&s,&t);
		t=n+t;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&w[i]);
			add(i,n+i,w[i]);
			add(n+i,i,0);
		}
			
		while(m--)
		{
			scanf("%d%d",&u,&v);
			add(n+u,v,w[u]);
			add(v,n+u,0);
			add(n+v,u,w[v]);
			add(u,n+v,0);
		}
		printf("%lld\n",Dinic());
	}
	
	return 0;
}