Description
n个点的无向图，问最少删掉几个点，使得图不连通
n<=50 m也许可以到完全图？
Solution
最少，割点，不连通，可以想到最小割。
发现，图不连通，必然存在两个点不连通。
枚举源点汇点，要让源点汇点不连通。源点汇点不能割掉
网络建图：
为了割的是边，所以要点转化成边。
对于每个x，建立x‘=x+n，对于不是S、T的点（因为S、T不能割掉），x向x’连一条边权为1的边
对于原图的边e(x,y) x’->y 连接inf的边，y‘->x连接inf的边。
边权保证割的是点，不是边。
x‘->y连边保证，想走这条边，必须经过x。
源点汇点不唯一，所以要n^2枚举。
但是要保证S，T不直接相连，否则不可能分开。
（如果钦定0是源点，枚举汇点的话，可以hack掉
假设最优解必须割掉0，那么就ans大了
但是数据水）
然后每次重新建图。
跑dinic最小割，所有的最小割取min即可。
题目一些小坑：
1.图不连通？没关系，可以枚举得到最小割为0
2.m=0，同上
3.如果完全图?没有S、T满足不直接相邻，那么一定就是n
fl记录一下有没有dinic过即可。
4.n=1？同上fl可以判断。
Code
#include<cstdio>#include<iostream>#include<cstdlib>#include<algorithm>#include<cstring>#include<queue>#define numb ch-‘0‘using namespace std;const int N=52;const int inf=0x3f3f3f3f;int n,m;char ch;void rd(int &x){ ???x=0; ???while(!isdigit(ch=getchar())); ???for(x=numb;isdigit(ch=getchar());x=x*10+numb);}struct node{ ???int nxt,to; ???int w;}e[2*N*N+N];int hd[2*N],cnt=1;bool con[N][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;}queue<int>q;int d[2*N];int s,t;void pre(){ ???memset(hd,0,sizeof hd); ???cnt=1; ???for(int i=1;i<=n;i++){ ???????for(int j=1;j<=n;j++){ ???????????if(j==i) continue; ???????????if(con[i][j]){ ???????????????????????????????add(i+n,j,inf/2); ???????????????add(j,i+n,0); ???????????} ???????} ???????if(i!=s&&i!=t) add(i,i+n,1),add(i+n,i,0); ???}}bool bfs(){ ???while(!q.empty())q.pop(); ???memset(d,0,sizeof d); ???d[s+n]=1; ???q.push(s+n); ???while(!q.empty()){ ???????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){ ???????????????d[y]=d[x]+1; ???????????????q.push(y); ???????????????if(y==t) return 1; ???????????} ???????} ???} ???return 0;}int lp=0;int dfs(int x,int flow){ ???if(x==t) return flow; ???int rest=flow; ???for(int i=hd[x];i&&rest;i=e[i].nxt){ ???????int y=e[i].to; ???????if(d[y]==d[x]+1&&e[i].w){ ???????????int k=dfs(y,min(rest,e[i].w)); ???????????if(!k) d[y]=0; ???????????rest-=k; ???????????e[i].w-=k; ???????????e[i^1].w+=k; ???????} ???} ???return flow-rest;}int wrk(){ ???pre(); ???int ret=0; ???int flow; ???while(bfs()){ ???????while(flow=dfs(s+n,inf)) ret+=flow; ???} ???return ret;}int ans;bool fl;void clear(){ ???memset(hd,0,sizeof hd); ???cnt=1; ???memset(con,0,sizeof con); ???ans=inf; ???fl=false;}int main(){ ???int x,y; ???while(scanf("%d",&n)!=EOF){ ???????clear(); ???????scanf("%d",&m); ???????for(int i=1;i<=m;i++){ ???????????rd(x);rd(y); ???????????x++;y++; ???????????con[x][y]=con[y][x]=1; ???????} ???????for(int i=1;i<=n;i++){ ???????????for(int j=i+1;j<=n;j++){ ???????????????if(con[i][j]) continue; ???????????????fl=true; ???????????????s=i,t=j; ???????????????int tmp=wrk(); ???????????????ans=min(ans,tmp); ???????????} ???????} ???????if(!fl) ans=n; ???????printf("%d\n",ans); ???} ???return 0;}这个题，体现了“点边转化”，“容量inf”的处理思想。
点边转化：把点的信息转移到边上，或者边信息转移到点上。
点变成边：拆点，两个点之间的边信息是点的信息。并且要保证，实际经过这个点，必须经过这个边。
一般从上面的点x‘向下面y连边。
边变成点：把边拆成两个，中间加一个点，记录边的信息。
POJ 1966 Cable TV Network 【经典最小割问题】
原文地址：https://www.cnblogs.com/Miracevin/p/9611007.html