您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 2744 [HEOI2012] 朋友圈：補圖最大獨立集 + 二分圖匹配

編輯：關於C++

題目大意

兩國 A、B，各自內部及跨國有「朋友」關係。求最大「朋友圈」（即所有人兩兩互為朋友的最大集合，也就是最大團）。

A 國：a xor b 為奇數 → 朋友
B 國：a xor b 為偶數或 (a or b) 二進制 1 的個數為奇數 → 朋友
A-B 跨國朋友關係輸入給定
|A| ≤ 200, |B| ≤ 200 (第一類) 或 |A| ≤ 10, |B| ≤ 3000 (第二類)

核心轉化：最大團 = 補圖最大獨立集

在補圖中，朋友圈變為「無邊相連的點集」= 獨立集。

補圖結構分析

A 國補圖：原圖中「xor 為奇數」有邊 → 補圖中「xor 為偶數」有邊。
→ 奇數點兩兩相連、偶數點兩兩相連 → 兩個團 → 最多只能選 2 個點（一奇一偶）。

B 國補圖：原圖邊條件較複雜，但補圖中可證：
奇數點之間無邊、偶數點之間無邊 → 二分圖 (奇偶分部)。

解題策略：枚舉 A 國選擇 + B 國最大獨立集

A 國最多選 2 人 → 枚舉三種情況：

選 0 人 → B 國可選所有人
選 1 人 (枚舉 A 中每個人) → B 國僅保留與其為朋友的人
選 2 人 (枚舉 A 中一奇一偶) → B 國僅保留同時與兩人為朋友的人

對每種情況，在 B 國誘導子圖上求最大獨立集。二分圖最大獨立集 = |V| - 最大匹配 (Kőnig 定理)。

完整程式碼 (C++)

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

const int MAXN = 3005;
const int MAXM = 5000005;

int na, nb, m;
int a[MAXN], b[MAXN];
bool g[MAXN][MAXN];        // A-B 原圖朋友關係
bool tag[MAXN];            // B 國當前可用點
int match[MAXN], head[MAXN], vst[MAXN];
struct Edge { int to, next; } e[MAXM];
int ecnt = 0;

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

// 建立 B 國補圖（二分圖：左部奇數，右部偶數）
void build_B_complement() {
    ecnt = 0;
    fill(head, head + nb + 1, 0);
    for (int i=1; i<=nb; ++i) if (b[i] & 1) {
        for (int j=1; j<=nb; ++j) if (!(b[j] & 1)) {
            int tmp = b[i] | b[j], cnt = __builtin_popcount(tmp);
            if (cnt % 2 == 0) add_edge(i, j);  // 補圖有邊
        }
    }
}

// 匈牙利算法 DFS
bool dfs(int u) {
    if (!tag[u]) return false;
    for (int i=head[u]; i; i=e[i].next) {
        int v = e[i].to;
        if (tag[v] && !vst[v]) {
            vst[v] = 1;
            if (!match[v] || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

// 計算當前 tag 下 B 國最大獨立集大小
int max_independent_set_B() {
    fill(match, match + nb + 1, 0);
    int matching = 0;
    for (int i=1; i<=nb; ++i) if ((b[i] & 1) && tag[i]) {
        fill(vst, vst + nb + 1, 0);
        if (dfs(i)) ++matching;
    }
    int total = 0;
    for (int i=1; i<=nb; ++i) if (tag[i]) ++total;
    return total - matching;  // 最大獨立集 = |V| - 最大匹配
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> na >> nb >> m;
    for (int i=1; i<=na; ++i) cin >> a[i];
    for (int i=1; i<=nb; ++i) cin >> b[i];
    
    memset(g, 0, sizeof(g));
    for (int i=0; i<m; ++i) {
        int x, y; cin >> x >> y;
        g[x][y] = true;
    }
    
    build_B_complement();
    
    int ans = 0;
    
    // 情況 1：A 選 0 人
    fill(tag, tag + nb + 1, 1);
    ans = max(max_independent_set_B(), ans);
    
    // 情況 2：A 選 1 人
    for (int i=1; i<=na; ++i) {
        fill(tag, tag + nb + 1, 0);
        for (int j=1; j<=nb; ++j) if (g[i][j]) tag[j] = 1;
        ans = max(ans, 1 + max_independent_set_B());
    }
    
    // 情況 3：A 選 2 人 (一奇一偶)
    for (int i=1; i<=na; ++i) if (a[i] & 1)
        for (int j=1; j<=na; ++j) if (!(a[j] & 1)) {
            fill(tag, tag + nb + 1, 0);
            for (int k=1; k<=nb; ++k) if (g[i][k] && g[j][k]) tag[k] = 1;
            ans = max(ans, 2 + max_independent_set_B());
        }
    
    cout << ans << '\n';
    return 0;
}