【题解】【P4662 [BalticOI 2008]黑手党】

Analysis

无向图有源汇最小割的模板题，无向图和有向图的最小割其实没有区别，把无向图的边看成两条有向边即可。
本题中要割点,只需把点拆成入点和出点，从入点向出点连容量为点权的边，原图中的边(x,y)从x的出点连向y的入点，容量为inf（避免被割）
要求方案，则从起点开始dfs，只经过所有边权不为0的边，设遍历的点集为S，补集为T，从S连向T的边集即为答案。
注意，还要判断这条边是否为反向边，只有原图中的边才有可能被割。
在本题中，可以通过判断两端点是否为一对出点和入点达到同样效果。

Code

#include
using namespace std;
//#define int long long
inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) putchar('-'),x=~(x-1);
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=410,M=1e5+100,inf=1e9;
int n,m,s,t,c[N];
vectorv;
struct node{
	int nxt,to,w;
}e[M<<1];
int hd[N],cnt=1,now[N],d[N];
void add(int x,int y,int z)
{
	e[++cnt].nxt=hd[x],e[cnt].to=y,e[cnt].w=z,hd[x]=cnt;
	e[++cnt].nxt=hd[y],e[cnt].to=x,e[cnt].w=0,hd[y]=cnt;
}
queueq;
bool bfs()
{
	while(q.size()) q.pop();
	for(int i=1;i<=n+n;++i) now[i]=hd[i],d[i]=0;
	d[s]=1;q.push(s);
	while(q.size())
	{
		int x=q.front();q.pop();
		for(int i=hd[x];i;i=e[i].nxt)
		{
			int y=e[i].to;if(d[y]||e[i].w==0) continue;
			d[y]=d[x]+1;q.push(y);
			if(y==t) return 1;
		}
	}
	return 0;
}
int dinic(int x,int flow)
{
	if(x==t) return flow;
	int rest=flow;
	for(int i=now[x];i&&rest;i=e[i].nxt)
	{
		int y=e[i].to;now[x]=i;
		if(d[y]==d[x]+1){
			int k=dinic(y,min(rest,e[i].w));
			if(k