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可以判断。
我犯得错误：还是没有注意到点数拆点后是2*n的事实，开始hd[50]开小了，改成hd[100]才行的。
图中的实际点，和创造的虚拟点的数量要弄清楚。（话说不是RE而是WA？）
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
",ans);
}
return 0;
}
这个题，体现了“点边转化”，“容量inf”的处理思想。
点边转化：把点的信息转移到边上，或者边信息转移到点上。
点变成边：拆点，两个点之间的边信息是点的信息。并且要保证，实际经过这个点，必须经过这个边。
一般从上面的点x'向下面y连边。
边变成点：把边拆成两个，中间加一个点，记录边的信息。