洛谷 P1345 奶牛的电信:(最小点割的处理)

题目大意:给定一个连通的无向图，问至少要删掉多少个点才能使得两个点s,t不连通。
根据最大流最小割定理，我们可以通过求s->t的最大流而获得s->t的最小割，不过这个割是一个边集而不是点集。因此需要将点割转化为边割。

抠一个洛谷题解中:interestingLSY 用户的图
将每个点分成两个点，一个点是该点的入点（即原图中指向这个点的边现在指向该点），另一个点是该点的出点(即原图中该点的出边现通过这个点指出)，然后在入点到出点间加一条有向边。这样 每个点的这条边是唯一的，如果割掉这条边就相当于割掉了这个点(因为其他相连的点都走不通了，这和删除这个点的效果是一样的)，这样就可以转化为求边割集。
关于建图:可以观察到无向图被这样处理成了有向图，原图中的出边是不影响的，因此出边容量设为INF,黄色的边(即新加的入边)容量设为1，用网络流算法跑一下即可。

关于算法的起点:这样处理后我们不能以原点s为起点，因为s点现在只有一条容量为1的出边，这样跑不出最大流，应该以s的出点为起点，出点连的边是原图中s点的出边，容量为INF。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e3+10;
int n,m,s,t;
vector<int> g[maxn];
struct ss{
 	int v,w,nxt;
}edg[500*maxn];
int head[maxn],cnt,deep[maxn],cur[maxn];
void init(){
 	cnt = 0;
 	memset(head,-1,sizeof(head));
}
void add(int x,int y,int w){
 	edg[cnt].v=y;
 	edg[cnt].nxt=head[x];
 	edg[cnt].w=w;
 	head[x]=cnt++;
}
bool bfs(int s,int t){
 	memset(deep,0,sizeof(deep));
 	queue<int> pq;
 	pq.push(s);
 	deep[s]=1;
 	while(!pq.empty()){
 		int top=pq.front();
  		pq.pop();
  		for(int i = head[top]; i + 1; i = edg[i].nxt){
   			int v=edg[i].v;
   			int w=edg[i].w;
   			if(w>0&&!deep[v]){
    				deep[v]=deep[top]+1;
    				pq.push(v);
   			}
  		}
 	}
 	return deep[t]!=0;
}
int dfs(int s,int t,int flow){
 	if(s==t) return flow;
 	int res=0;
 	for(int &i = cur[s]; i+1 ; i=edg[i].nxt){
 		int v=edg[i].v;
  		int &w=edg[i].w;
  		int x = 0;
  		if(deep[v]==deep[s]+1&&w>0){
   			x=dfs(v,t,min(flow,w));
   			w-=x;flow-=x;res+=x;edg[i^1].w+=x;
   			if(!flow) break;
  		}
 	}
 	if(!res) deep[s]=-2;
 	return res;
}
int dinic(int s,int t){
 	int res=0;
 	while(bfs(s,t)){
  		for(int i = 1; i <= maxn; i++) 
   			cur[i]=head[i];
  		res+=dfs(s,t,0x3f3f3f3f);
 	}	
 	return res;
}
int main(){
 	scanf("%d%d%d%d",&n,&m,&s,&t);
 	int x,y;
 	init();
 	for(int i = 1; i <= m; i++){
  		scanf("%d%d",&x,&y);
  		g[x].push_back(y);
  		g[y].push_back(x);
 	}
 	for(int i = 1; i <= n; i++){
  		add(i,i+n,1);
  		add(i+n,i,0);
  		for(int j = 0; j < g[i].size(); j++){
   			add(i+n,g[i][j],0x3f3f3f3f);
   			add(g[i][j],i+n,0);
  		}
 	}	
	printf("%d\n",dinic(s+n,t));
}