POJ 1274 The Perfect Stall — 二分圖最大匹配 / 網絡流

題目大意

N≤200 隻奶牛，M≤200 個牛棚。每頭牛有一份願意產奶的牛棚列表。每棚只能容納一頭牛，每牛只能分配一棚。求最大匹配數。

模型轉化

經典二分圖最大匹配：左部奶牛，右部牛棚，邊表示「願意」。亦可建源點、匯點跑最大流（Dinic/SAP/ISAP）。

匈牙利算法（DFS 版）核心碼

#include 
using namespace std;
const int MAXN = 205;
int n, m;
vector G[MAXN];
int matchR[MAXN];
bool vis[MAXN];

bool dfs(int u) {
    for (int v : G[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        if (matchR[v] == 0 || dfs(matchR[v])) {
            matchR[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m) {
        for (int i=1;i<=n;++i) G[i].clear();
        for (int i=1;i<=n;++i) {
            int s; cin >> s;
            while (s--) { int stall; cin >> stall; G[i].push_back(stall); }
        }
        fill(matchR, matchR+m+1, 0);
        int ans = 0;
        for (int i=1;i<=n;++i) {
            fill(vis, vis+m+1, false);
            if (dfs(i)) ++ans;
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 匈牙利 O(N·E)，N,M≤200 極快。
• Dinic O(E√V) 亦可，碼量稍大。

關鍵點

1. 輸入多組測試，直到 EOF。
2. 牛棚編號 1~M，直接作為右部節點。
3. 輸出單個整數，每行一組答案。