1660 Cable TV Network

程式碼

// author: Piau
#include <bits/stdc++.h>
using namespace std;

#define INF LONG_LONG_MAX / 1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long

vector<int> dep, cur;
vector<vector<int>> g, bu;
int n, m, s, t;

bool bfs() {
    fill(all(dep), -1);
    dep[s] = 0;
    queue<int> q;
    q.push(s);
    while (q.size()) {  // u -> v
        int u = q.front();
        q.pop();
        for (int v = 0; v < n * 2; v++)
            if (g[u][v] && !~dep[v]) {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
    }
    return ~dep[t];
}

int dfs(int u, int mn) {
    if (!mn) return 0;
    if (u == t) return mn;

    for (int& v = cur[u]; v < n * 2; v++) {
        if (dep[u] + 1 == dep[v] && g[u][v]) {
            if (int go = dfs(v, min(mn, g[u][v]))) {
                g[u][v] -= go;
                g[v][u] += go;
                return go;
            }
        }
    }
    return 0;
}

int dinic() {
    int flow = 0;
    while (bfs()) {
        fill(all(cur), 0);
        while (int go = dfs(s, INF)) flow += go;
    }
    return flow;
}

signed main() {
    WA();
    for (; cin >> n >> m;) {
        g.assign(n * 2, vector<int>(n * 2, 0));
        dep.assign(n * 2, 0);
        cur.assign(n * 2, 0);
        for (int i = 0; i < n; i++) g[i][i + n] = 1;
        for (int k = m; k--;) {
            char c;
            int a, b;
            cin >> c >> a >> c >> b >> c;
            g[a + n][b] = INF;
            g[b + n][a] = INF;
        }
        bu = g;
        int ans = n;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                g = bu;
                s = i + n;
                t = j;
                ans = min(ans, dinic());
            }
        }
        cout << ans << '\n';
    }
}