题目链接： POJ 1966 Cable TV Network

题目大意：

一张 \(N\) 个点的无向图，求最少删去多少点后可以使得图不连通。

\(0\leq N\leq 50\)

思路：

这里有一个小技巧：点转边

将每个点拆成一个出点和一个入点，入点连接所有进边，出点连接所有出边，两点间连一条权值为 \(1\) 的边，代表删除这个点的代价，而连在原先点与点之间的边权值设为 \(\infty\)，防止删除了真正的边。

然后这题就转化成最小割了，枚举源点 \(S\) 和汇点 \(T\) ，将最小割更新答案即可。

细节：

挺板子的，就是 \(S\) 和 \(T\) 不能是同一个点即可， \(S\) 是该点的出点， \(T\) 是另外那个点的入点。

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<fstream>
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define N 105
#define M 5200
#define Inf 0x3f3f3f3f
using namespace std;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int head[N],to[M],nxt[M];
int cnt,s,t;
int val[M],cap[M],d[N];
bool conn[N][N];
queue<int> q;
void init(){mem(head,-1),cnt=-1,mem(conn,false);}
void add_e(int a,int b,int w){
    nxt[++cnt]=head[a],head[a]=cnt,to[cnt]=b;
    val[cnt]=cap[cnt]=w;
    if(w)add_e(b,a,0);
}
bool bfs(){
    mem(d,0);
    while(!q.empty())q.pop();
    d[s]=1,q.push(s);
    while(!q.empty()){
        int cur=q.front(); q.pop();
        for(int i=head[cur];~i;i=nxt[i]){
            if(cap[i]&&!d[to[i]]){
                d[to[i]]=d[cur]+1;
                q.push(to[i]);
                if(to[i]==t)return true;
            }
        }
    }
    return false;
}
int dinic(int x,int flow){
    if(x==t)return flow;
    int rest=flow,k;
    for(int i=head[x];(~i)&&rest;i=nxt[i]){
        if(cap[i]&&d[to[i]]==d[x]+1){
            k=dinic(to[i],min(cap[i],rest));
            if(!k)d[to[i]]=0;
            cap[i]-=k,cap[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
int main(){
    int n,m,a,b;
    while(cin>>n>>m){
        if(n==1){
            cout<<"1\n";
            continue;
        }
        init();
        rep(i,1,m){
            a=read(),b=read(),conn[a][b]=true;
            add_e(a+n,b,Inf),add_e(b+n,a,Inf);
        }
        rep(i,0,n-1)add_e(i,i+n,1);
        int ans=n;
        rep(i,0,n-1)rep(j,0,n-1){
            if(conn[i][j]||i==j)continue;
            rep(k,0,cnt)cap[k]=val[k];
            s=i+n,t=j;
            int maxflow=0,flow;
            while(bfs()){
                while(flow=dinic(s,Inf))maxflow+=flow;
            }
            ans=min(ans,maxflow);
        }
        cout<<ans<<endl;
    }
    return 0;
}