HDU 3829 貓狗大戰：二分圖最大獨立集模型詳解

問題重述

動物園有 n 隻貓、m 條狗，p 個小孩。每個小孩有一個喜歡的動物和一個討厭的動物（喜歡貓必討厭狗，反之亦然）。小孩開心的條件：喜歡的動物留在園內，討厭的動物被移走。求移走哪些動物能使最多小孩開心。

模型轉化

• 兩個小孩若「喜歡的動物 = 另一個討厭的動物」或「討厭的動物 = 另一個喜歡的動物」，則兩者產生衝突，不能同時開心。
• 構建衝突圖：點為小孩，邊為衝突關係。問題轉化為求最大獨立集（無邊相連的最大點集）。
• 二分圖性質：最大獨立集 = 總頂點數 - 最大匹配數（Kőnig 定理）。
• 將小孩按喜歡動物類型分為左右兩部（喜貓 / 喜狗），衝突邊只會跨部出現，構成二分圖。

算法流程

1. 讀入每個小孩的喜歡/討厭動物字符串。
2. 雙重循環檢測衝突，建立二分圖邊（源點連左部，右部連匯點，容量均為 1）。
3. Dinic 算法求最大流 = 最大匹配數。
4. 答案 = p - 最大匹配數 / 2（每條匹配邊被雙向添加，需除 2）。

核心代碼 (Dinic 模板)

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;

struct Edge { int to, cap, rev; };
vector<Edge> G[MAXN];
int level[MAXN], iter[MAXN];

void add_edge(int from, int to, int cap) {
    G[from].push_back({to, cap, (int)G[to].size()});
    G[to].push_back({from, 0, (int)G[from].size() - 1});
}

void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> q; level[s] = 0; q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto &e : G[v])
            if (e.cap > 0 && level[e.to] < 0)
                level[e.to] = level[v] + 1, q.push(e.to);
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < (int)G[v].size(); i++) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0, f;
    while (1) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
}

char like[510][10], dislike[510][10];
int main() {
    int n, m, p;
    while (scanf("%d%d%d", &n, &m, &p) != -1) {
        for (int i = 0; i < MAXN; i++) G[i].clear();
        for (int i = 1; i <= p; i++) scanf("%s%s", like[i], dislike[i]);
        // 建圖
        for (int i = 1; i <= p; i++) add_edge(0, i, 1);
        for (int i = p+1; i <= 2*p; i++) add_edge(i, 2*p+1, 1);
        for (int i = 1; i <= p; i++)
            for (int j = i+1; j <= p; j++)
                if (strcmp(like[i], dislike[j]) == 0 || strcmp(dislike[i], like[j]) == 0) {
                    add_edge(i, j+p, 1);
                    add_edge(j, i+p, 1);
                }
        int ans = max_flow(0, 2*p+1) / 2;
        printf("%d\n", p - ans);
    }
    return 0;
}