Cable TV Network

思路：
无向图不连通则必有两个点不连通，枚举两个点，求在剩下的个节点中最少去掉多少个点，可以使和不连通，在每次枚举的结果中取最小值就是这题的答案。
拆点的两种方式：
1.入点和出点分别是和，需要知道有多少个点
2.入点和出点分别是和

点的出边到的入边的最小割就是需要去掉的点，枚举完后把反向边的容量加回去就可以把残余网络复原了。

MyCode:

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int maxn=110,maxm=6e3+10;

int head[maxn],Next[maxm],to[maxm],edge[maxm],tot=1,d[maxn],s,t,now[maxn],ans;
queue<int>q;
void add(int x,int y,int z) {
    to[++tot]=y; Next[tot]=head[x]; head[x]=tot; edge[tot]=z;
    to[++tot]=x; Next[tot]=head[y]; head[y]=tot; edge[tot]=0;
} 
bool bfs() {
    memset(d,0,sizeof d);
    while(q.size()) q.pop();
    q.push(s); d[s]=1; now[s]=head[s];
    while(q.size()) {
        int x=q.front(); q.pop();
        for(int i=head[x],y;i;i=Next[i]) {
            if(edge[i] && !d[y=to[i]]) {
                q.push(y);
                now[y]=head[y];
                d[y]=d[x]+1;
                if(y==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow) {
    if(x==t) return flow;
    int rest=flow,k,i,y;
    for(i=now[x];i && rest; i=Next[i]) {
        if(edge[i] && d[y=to[i]] == d[x] + 1) {
            k=dinic(y,min(rest,edge[i]));
            if(!k) d[y]=0;
            edge[i]-=k; edge[i^1]+=k;
            rest-=k;
        }
    }
    now[x]=i;
    return flow - rest;
}
inline void work() {
    int flow(0),maxflow(0);
    while(bfs())
        while((flow=dinic(s,0x3f3f3f3f))) {
            maxflow+=flow;
            if(maxflow>=ans) return;
        }
    ans=min(ans,maxflow);
}
int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)) {
        ans=n; tot=1;
        memset(head,0,sizeof head);
        for(int i=0;i<n;++i) add(i<<1,i<<1|1,1);
        for(int i=1,x,y;i<=m;++i) {
            scanf(" (%d,%d)",&x,&y);
            add(x<<1|1,y<<1,0x3f3f3f3f);
            add(y<<1|1,x<<1,0x3f3f3f3f);
        }
        for(int i=0;i<n;++i)
        for(int j=0;j<i;++j) {
            s=i<<1|1,t=j<<1;
            work();
            for(int k=2;k<tot;k+=2) if(edge[k^1]){
                edge[k]+=edge[k^1]; edge[k^1]=0;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}