有线电视网络

AcWing-381-有线电视网络

分析

见《进阶指南》第448页。

实现

#include <iostream>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 52, M = 1000010;
struct edge {
    int to, next, w;
};
edge e[M];
int idx, head[2 * N];
struct node {
    int u, v;
};
int n, m, s, t;
node a[N * N];
int d[2 * N], arc[2 * N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;

    e[idx].w = 0;
    e[idx].to = u;
    e[idx].next = head[v];
    head[v] = idx ++;
}
bool bfs () {
    memset(d, 0, sizeof(d));
    d[s] = 1;
    arc[s] = head[s];
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;
            if (d[to] == 0 && w) {
                d[to] = d[cur] + 1;
                arc[to] = head[to];
                q.push(to);
                if (to == t) return true;
            }
        }
    }
    return false;
}
int dinic (int cur, int flow) {
    if (cur == t) return flow;

    int rest = flow;
    for (int i = arc[cur]; i != -1 && rest; i = e[i].next) {
        int to = e[i].to, w = e[i].w;
        arc[cur] = i;
        if (d[to] == d[cur] + 1 && w) {
            int k = dinic(to, min(rest, w));
            if (k == 0) d[to] = 0;
            e[i].w -= k;
            e[i ^ 1].w += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int main () {
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 1; i <= m; ++ i)
            scanf(" (%d,%d)", &a[i].u, &a[i].v);

        int res = inf;
        for (s = 0; s < n; ++ s) {
            for (t = 0; t < n; ++ t) {
                if (s == t) continue;
                idx = 0;
                memset(head, -1, sizeof(head));
                int max_flow = 0, flow;
                for (int i = 0; i < n; ++ i) {
                    if (i == s || i == t) {
                        add_edge(i, i + n, inf);
                    } else {
                        add_edge(i, i + n, 1);
                    }
                }
                for (int i = 1; i <= m; ++ i) {
                    int u = a[i].u, v = a[i].v;
                    add_edge(u + n, v, inf);
                    add_edge(v + n, u, inf);
                }
                while (bfs() == true)
                    while (flow = dinic(s + n, inf))
                        max_flow += flow;
                res = min(res, max_flow);
            }
        }
        if (n <= 1 || res == inf) res = n;
        printf("%d\n", res);
    }
    return 0;
}