P4249 [WC2007] 剪刀石头布

· · 题解

如果一个三元组不是三元环，那么有一个点的出度为 2。假定一个点的出度为 d，那么它会使得三元环减少 \frac{d(d-1)}{2}，那么最终答案为：

\binom n 3 - \sum_{i=1}^n \frac{d(d-1)}{2}

考虑最小费用最大流。每个人向汇点连容量为 n 的边，源点向每个不确定的边连边、边向两个人连边，容量均为 1。

一个人的贡献可以看成 0+1+\cdots+d_i-1，这是等差数列的费用。套路地，考虑拆点，拆成 n 个，费用依次为 0,1,\cdots,n-1 即可。

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

int n, m; 
int a[105][105], d[105], id[105][105]; 

struct Graph {
    struct edge {
        int u, v, w, c;
        edge(int u = 0, int v = 0, int w = 0, int c = 0) : 
            u(u), v(v), w(w), c(c) {}
    };

    int n, m, s, t, cur[7005], d[7005];
    bool inq[7005];
    vector<int> G[7005];
    vector<edge> edges;

    inline void addedge(int u, int v, int w, int c) {
        edges.emplace_back(edge(u, v, w, c));
        G[u].emplace_back(edges.size() - 1); 
        edges.emplace_back(edge(v, u, 0, -c));
        G[v].emplace_back(edges.size() - 1); 
    }

    bool SPFA(void) {
        memset(cur, 0, sizeof(cur));
        memset(d, 0x3f, sizeof(d));
        queue<int> q; q.push(s); d[s] = 0; inq[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop(); inq[u] = false;
            for (int i = 0; i < G[u].size(); ++i) {
                edge &e = edges[G[u][i]];
                if (e.w && d[e.v] > d[u] + e.c) {
                    d[e.v] = d[u] + e.c;
                    if (!inq[e.v]) q.push(e.v), inq[e.v] = true;
                }
            }
        }
        return d[t] < 0x3f3f3f3f;
    }

    int cost;
    bool vis[7005];
    int dinic(int x, int res) {
        if (x == t) return res;
        int flow = 0; vis[x] = true;
        for (int i = cur[x]; i < G[x].size() && res; ++i) {
            edge &e = edges[G[x][i]]; cur[x] = i;
            int c = min(res, e.w);
            if (!vis[e.v] && c && d[e.v] == d[x] + e.c) {
                int k = dinic(e.v, c);
                flow += k; cost += k * e.c; res -= k;
                edges[G[x][i]].w -= k; edges[G[x][i] ^ 1].w += k;
            }
        }
        if (!flow) d[x] = 0x3f3f3f3f; vis[x] = false;
        return flow;
    }
    int MCMF(int S, int T) {
        s = S; t = T; 
        int maxflow = 0, flow;
        while (SPFA()) while (flow = dinic(s, 1e9)) maxflow += flow;
        return cost; 
    }
} G;

int main(void) {
    ios::sync_with_stdio(0); 

    cin >> n; int S = 0, T = 7001; 
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
        cin >> a[i][j]; 
        if (a[i][j] == 1) ++d[i]; 
    }
    for (int i = 1, idx = n; i <= n; ++i) 
        for (int j = i + 1; j <= n; ++j) if (a[i][j] == 2) {
            G.addedge(S, ++idx, 1, 0); 
            G.addedge(idx, i, 1, 0); id[i][j] = G.edges.size() - 2; 
            G.addedge(idx, j, 1, 0); id[j][i] = G.edges.size() - 2; 
        }
    int ans = 0; 
    for (int i = 1; i <= n; ++i) {
        ans += d[i] * (d[i] - 1) / 2; 
        for (int j = d[i] + 1; j <= n; ++j)
            G.addedge(i, T, 1, j - 1); 
    }
    ans += G.MCMF(S, T); 
    cout << n * (n - 1) * (n - 2) / 6 - ans << "\n"; 
    for (int i = 1; i <= n; ++i, cout << "\n")
        for (int j = 1; j <= n; ++j, cout << " ") {
            if (a[i][j] < 2) cout << a[i][j]; 
            else cout << 1 - G.edges[id[i][j]].w; 
        }
    return 0;
}