POJ 3692 二分圖最大匹配：最大團轉化

問題描述

班級有 g 個女生、b 個男生（g,b ≤ 200）。女生之間互相認識，男生之間互相認識。給出 m 對「女生-男生」認識關系。求最大「團」（所有人兩兩認識）的大小。

圖論轉化

• 構建圖：不認識的 pair 連邊。女生間無邊，男生間無邊，只有一部分女生-男生之間有邊 → 二分圖。
• 原圖中「團」= 補圖中「獨立集」。
• 二分圖中：最大獨立集 = |V| - 最大匹配（Kőnig 定理）。
• 所以：最大團 = 補圖最大獨立集 = |V| - 補圖最大匹配。
• 補圖即「不認識」圖，直接在補圖上跑最大匹配（匈牙利/DFS）。

算法步驟

1. 讀入 g, b, m。
2. 建立鄰接矩陣 know[g][b]，標記認識關系。
3. 構建補圖邊：對每個女生 i、男生 j，若 !know[i][j] 則加邊 i → g+j。
4. 跑二分圖最大匹配（匈牙利算法，DFS 版）。
5. 答案 = g + b - max_match。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 405;
int g, b, m;
bool know[205][205];
vector adj[MAXV];
int match[MAXV];
bool vis[MAXV];

bool dfs(int u) {
    for (int v : adj[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int hungarian() {
    fill(match, match+g+b, -1);
    int ans = 0;
    for (int u = 0; u < g; ++u) {
        fill(vis, vis+g+b, false);
        if (dfs(u)) ++ans;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> g >> b >> m) {
        for (int i=0;i> x >> y;
            know[x-1][y-1] = true;  // 1-based 輸入
        }
        for (int i=0;i

複雜度
匈牙利 O(V·E) = O((g+b)·g·b) ≤ 400×40000 = 1.6×107，極快。g,b ≤ 200 也可用 HK 算法 O(√V·E) 但無必要。

關鍵點總結

「互相認識」團 → 補圖獨立集。
補圖為二分圖 → 最大獨立集 = |V| - 最大匹配。
直接在補圖跑匹配，無需構建原圖。