UVALive 貓狗投票：最大獨立集轉二分圖最大匹配

問題描述

有 N 張選票，每票要么「喜歡貓 X，討厭狗 Y」，要么「喜歡狗 X，討厭貓 Y」。選出一組貓和狗，使滿足的選票數最大。若一票的喜歡對象被選中且討厭對象未被選中，則該票滿足。

建模為最大獨立集

• 將「喜歡貓」的選票建為左部節點，「喜歡狗」的選票建為右部節點。
• 若兩票衝突（一票喜歡的貓 = 另一票討厭的貓，或一票喜歡的狗 = 另一票討厭的狗），則在兩節點間連邊。
• 衝突圖為二分圖。最大滿足票數 = 總票數 - 最小點覆蓋 = 總票數 - 最大匹配數（Kőnig 定理）。

算法流程

1. 讀入票數，分離貓票、狗票，記錄喜歡/討厭編號（字符串）。
2. 雙重循環檢查每對貓票-狗票是否衝突，建立鄰接表。
3. 匈牙利算法（DFS 增廣路）求最大匹配。
4. 答案 = V - matching。

參考代碼

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

const int MAXV = 510;
struct Vote { char like[5], dislike[5]; } cat[MAXV], dog[MAXV];
vector<int> G[MAXV];
int link[MAXV], catCnt, dogCnt, V;
bool vis[MAXV];

bool dfs(int u) {
    for (int v : G[u]) if (!vis[v]) {
        vis[v] = true;
        if (link[v] == -1 || dfs(link[v])) {
            link[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int c, d; scanf("%d%d%d", &c, &d, &V);
        catCnt = dogCnt = 0;
        char like[5], hate[5];
        for (int i = 0; i < V; ++i) {
            scanf("%s%s", like, hate);
            if (like[0] == 'C') {
                strcpy(cat[catCnt].like, like);
                strcpy(cat[catCnt].dislike, hate);
                G[catCnt++].clear();
            } else {
                strcpy(dog[dogCnt].like, like);
                strcpy(dog[dogCnt].dislike, hate);
                ++dogCnt;
            }
        }
        for (int i = 0; i < catCnt; ++i)
            for (int j = 0; j < dogCnt; ++j)
                if (!strcmp(cat[i].like, dog[j].dislike) ||
                    !strcmp(cat[i].dislike, dog[j].like))
                    G[i].push_back(j);
        memset(link, -1, sizeof(link));
        int match = 0;
        for (int i = 0; i < catCnt; ++i) {
            memset(vis, 0, sizeof(vis));
            if (dfs(i)) ++match;
        }
        printf("%d\n", V - match);
    }
    return 0;
}

複雜度

• 建圖：O(C·D·L)，L 為字符串長度（≤4）。
• 匈牙利：O(V·E)，V ≤ 500，E ≤ C·D，極快。