BZOJ 1305 [CQOI2009] 跳舞：最大流與二分答案解法

問題背景

有 n 個男孩和 n 個女孩，每首舞曲需配成 n 對。每個男孩不與同一女孩跳兩次。部分男女互相喜歡，其餘互不喜歡。每人最多接受 k 個不喜歡的異性舞伴。給定喜歡關係矩陣，求最多能跳幾首舞曲。

解題策略：最大流 + 二分答案

將問題轉化為最大流模型：

• 每個人拆分為三個節點：總節點、喜歡節點、不喜歡節點。
• 喜歡的男女之間連容量為 1 的邊；不喜歡的連容量為 1 的邊（經過不喜歡節點）。
• 源點連向男孩總節點，容量為二分的舞曲數 x；女孩總節點連向匯點，容量同 x。
• 喜歡節點容量無限（INF），不喜歡節點容量限制為 k。
• 二分 x，構圖跑 Dinic 最大流，若滿流（流量 = n*x）則可行。

核心代碼片段

inline void build(int x) {
    cnt = 1; memset(head, 0, sizeof(head));
    for (int i = 1; i <= n; ++i) {
        add_edge(s, f1(i), x); add_edge(f2(i), t, x);
        add_edge(f1(i), f1(i)+1, INF); add_edge(f2(i)+1, f2(i), INF);
    }
    if (k) for (int i = 1; i <= n; ++i)
        add_edge(f1(i), f1(i)+2, k), add_edge(f2(i)+2, f2(i), k);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (f[i][j]) add_edge(f1(i)+1, f2(j)+1, 1);
            else add_edge(f1(i)+2, f2(j)+2, 1);
}

複雜度分析

節點數 O(n)，邊數 O(n²)。Dinic 複雜度 O(E√V) 約 O(n²·√n)。二分範圍 0~n，總體 O(n²·√n·log n)，滿足 n≤50 限制。