有线电视网络（最小割）

题意

给定一张无向图，求最少去掉多少个点，可以使图不连通。点数(N leq 50)

思路

这里引用李煜东《算法竞赛进阶指南》给出的方法。

若无向图不连通，则图中必有两个点不连通，但这两个点是未知的。因此可以枚举源点(S)和汇点(T)，然后求去掉多少个点可以使得(S)和(T)不连通。答案为各次中的最小值。

“去掉最少的点使(S)和(T)不连通”的问题与最小割非常相似，只不过要割的是“点”而不是“边”，因此可以考虑拆点，将一个点拆成入点(x)和出点(x')。容易发现，在无向图中删去一个点，就等价于在网络中断开((x, x'))

入点向出点连容量是(1)的边。对于原无向图的每条边((x,y))，在网络中连有向边((x', y), (y', x)，容量是)infty$。

这道题包含两个技巧：第一是点边转化，第二是容量为(infty)的边具有防止割断的含义。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 55 * 2, M = N * N, inf = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int cur[N], d[N];

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

bool bfs()
{
    memset(d, -1, sizeof(d));
    queue<int> que;
    que.push(S);
    d[S] = 0, cur[S] = h[S];
    while(que.size()) {
        int t = que.front();
        que.pop();
        for(int i = h[t]; ~i; i = ne[i]) {
            int ver = e[i];
            if(d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                que.push(ver);
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i]) {
            int t = find(ver, min(f[i], limit - flow));
            if(!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while(bfs()) {
        while(flow = find(S, inf)) {
            res += flow;
        }
    }
    return res;
}

int main()
{
    while(cin >> n >> m) {
        memset(h, -1, sizeof(h));
        idx = 0;
        for(int i = 0; i < n; i ++) add(i, i + n, 1);
        for(int i = 0; i < m; i ++) {
            int a, b;
            scanf(" (%d,%d)", &a, &b);
            add(a + n, b, inf);
            add(b + n, a, inf);
        }
        int ans = n;
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < i; j ++) {
                S = n + i, T = j;
                ans = min(ans, dinic());
                for(int k = 0; k < idx; k += 2) {
                    f[k] += f[k ^ 1];
                    f[k ^ 1] = 0;
                }
            }
        }
        printf("%d
", ans);
    }
    return 0;
}