BZOJ 2597 WC2007 剪刀石頭布：費用流最大化三元環

題目大意

給定一個競賽圖（部分邊方向未定），需為未定向邊指定方向，使得圖中三元環（3-環）數量最大。

核心轉化：補集法

三個點之間若不構成三元環，則必有一個點擁有兩條出邊。因此：

三元環總數 = C(n,3) - Σ C(out_degree[x], 2)

最大化三元環 ⇔ 最小化 Σ C(out_degree[x], 2)。

最小費用最大流模型構建

1. 源點 S 向每個頂點 i (1..n) 連 n-1 條邊，容量 1，費用 0, 1, ..., n-2。
   第 k 條邊被選中代表該頂點第 k+1 條出邊，貢獻費用 k，對應 C(d,2) 的增量。
2. 每條原圖邊 (u,v) 建立一個中間節點 e。
   若邊可作 u 的出邊（原方向或未定），連 u → e，容量 1，費用 0。
   同理處理 v。
3. 每個中間節點 e 向匯點 T 連容量 1、費用 0 的邊，保證每條邊恰好分配一個方向。
4. 跑最小費用最大流，總流量為邊數 m，最小費用即為 Σ C(out_degree[x], 2) 的最小值。

關鍵代碼片段

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define M 11000
#define S 0
#define T 10999
#define INF 0x3f3f3f3f
using namespace std;

struct Edge { int to, f, cost, next; } table[1001001];
int head[M], tot = 1;
int n, cnt, ans, map[110][110], edge[110][110];

void Add(int x, int y, int f, int cost) {
    table[++tot] = {y, f, cost, head[x]};
    head[x] = tot;
}
void Link(int x, int y, int f, int cost) {
    Add(x, y, f, cost);
    Add(y, x, 0, -cost);
}

bool SPFA() {
    static int q[65540], f[M], from[M], cost[M];
    static bool v[M];
    int r = 0, h = 0;
    memset(cost, 0x3f, sizeof cost);
    q[++r] = S; f[S] = INF; cost[S] = 0; f[T] = 0;
    
    while (r != h) {
        int x = q[++h]; v[x] = 0;
        for (int i = head[x]; i; i = table[i].next) {
            if (table[i].f && cost[x] + table[i].cost < cost[table[i].to]) {
                cost[table[i].to] = cost[x] + table[i].cost;
                f[table[i].to] = min(f[x], table[i].f);
                from[table[i].to] = i;
                if (!v[table[i].to]) v[table[i].to] = 1, q[++r] = table[i].to;
            }
        }
    }
    if (!f[T]) return false;
    ans -= cost[T] * f[T];
    for (int i = from[T]; i; i = from[table[i^1].to]) {
        table[i].f -= f[T];
        table[i^1].f += f[T];
    }
    return true;
}

int main() {
    cin >> n; cnt = n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &map[i][j]);

    // S 到頂點：n-1 條邊，費用 0..n-2
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= n-2; ++j)
            Link(S, i, 1, j);

    // 處理每對頂點間的邊
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j) {
            Link(++cnt, T, 1, 0);  // 中間節點到 T
            if (map[i][j] == 0 || map[i][j] == 2)  // i→j 可行
                Link(i, cnt, 1, 0), edge[j][i] = tot-1;
            if (map[i][j] == 1 || map[i][j] == 2)  // j→i 可行
                Link(j, cnt, 1, 0), edge[i][j] = tot-1;
        }

    ans = n * (n-1) * (n-2) / 6;  // C(n,3)
    while (SPFA());
    cout << ans << endl;
    return 0;
}

複雜度與總結

• 節點數：O(n²)，邊數：O(n²)
• SPFA 平均 O(kE)，實際運行極快
• 關鍵洞察：將組合優化轉化為凸成本流問題，利用費用遞增邊建模 C(d,2)