ZOJ 3760 Treasure Hunting：二分圖最大獨立集 = 總權 - 最大流（最小割）

問題描述

有 n 個寶物，每個有坐標 (x, y) 和價值 v = x & y。若兩寶物滿足 gcd(x^y, m) > 1 則不能同時選。求最大總價值。

關鍵觀察：按 x^y 奇偶分組構成二分圖

• x^y 奇 ⇔ 奇偶性不同。題目給定 m 為偶數（或至少 P 為偶數），故奇數與奇數、偶數與偶數的 x^y 為偶數，至少有公因數 2，gcd ≥ 2 > 1，即同組內無邊（不衝突）。
• 衝突邊只存在於奇組與偶組之間。建立二分圖：左部奇組，右部偶組，衝突則連邊（容量 INF）。
• 源點連左部，容量 = 價值；右部連匯點，容量 = 價值。最大獨立集權值 = 總價值 - 最小點覆蓋權值 = 總價值 - 最大流。

代碼實現（Dinic 最大流）

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 4222;

struct Edge { int to, cap, next; } e[MAXN*MAXN];
int head[MAXN], ecnt, level[MAXN], q[MAXN];

void addEdge(int u, int v, int c) {
    e[ecnt] = {v, c, head[u]}; head[u] = ecnt++;
    e[ecnt] = {u, 0, head[v]}; head[v] = ecnt++;
}

bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    level[s] = 0; int qh=0, qt=0; q[qt++] = s;
    while (qh < qt) {
        int u = q[qh++];
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (e[i].cap && level[v] == -1) {
                level[v] = level[u] + 1;
                q[qt++] = v;
                if (v == t) return true;
            }
        }
    }
    return false;
}

int dfs(int u, int t, int f) {
    if (u == t) return f;
    int ret = 0;
    for (int i = head[u]; ~i && ret < f; i = e[i].next) {
        int v = e[i].to;
        if (e[i].cap && level[v] == level[u] + 1) {
            int d = dfs(v, t, min(e[i].cap, f - ret));
            e[i].cap -= d; e[i^1].cap += d;
            ret += d;
        }
    }
    if (!ret) level[u] = -1;
    return ret;
}

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        ecnt = 0; memset(head, -1, sizeof(head));
        int S = n+1, T = n+2;
        vector X(n+1), Y(n+1), val(n+1), parity(n+1);
        long long total = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &X[i], &Y[i]);
            val[i] = X[i] & Y[i];
            total += val[i];
            parity[i] = (X[i] ^ Y[i]) & 1;
            if (parity[i]) addEdge(S, i, val[i]);
            else addEdge(i, T, val[i]);
        }
        for (int i = 1; i <= n; ++i)
            if (parity[i])
                for (int j = 1; j <= n; ++j)
                    if (!parity[j] && gcd(X[i]^Y[i] ^ X[j]^Y[j], m) <= 1)
                        addEdge(i, j, INF);
        long long flow = 0;
        while (bfs(S, T)) flow += dfs(S, T, INF);
        printf("%lld\n", total - flow);
    }
    return 0;
}

複雜度

點數 n ≤ 1000，邊數 O(n^2) 最壞 1e6，Dinic 實際極快。