HDU 3879 & 3917：最大權閉合子圖建模與最大流求解

最大權閉合子圖核心模型

給定有向圖，每個節點有權值（正/負），每條邊表示依賴關係（選 u 必選 v）。求權值和最大的閉合子圖（滿足：若 u 在子圖中且 u→v，則 v 也在子圖中）。

標準構圖轉化為最小割/最大流：
- 源點 S 向正權節點連邊，容量 = 權值。
- 負權節點向匯點 T 連邊，容量 = |權值|。
- 原圖依賴邊容量 = INF。
- 答案 = 所有正權和 - 最大流值。

HDU 3879 Base Station

題意

無向圖，點權為負（建站成本），邊權為正（覆蓋收益）。選擇子圖最大化收益：收益 = 選中邊權和 - 選中點權和。條件：選邊必選其兩端點。

建模技巧

將「邊」作為新圖的節點（權值 = 邊權，正），原圖點作為節點（權值 = -點權，負）。新圖中：邊節點向其兩個端點連有向邊（容量 INF），表示選邊必選端點。套用最大權閉合模型即可。

代碼關鍵片段

void read_build() {
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cpy[i]);
        adde(i, tt, cpy[i]); // 原圖點權為負，向匯點連邊
    }
    int aa, bb, cc;
    int numv = n + 1;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &aa, &bb, &cc);
        sumz += cc; // 正權和累積
        adde(numv, aa, INF); // 邊節點 -> 端點1
        adde(numv, bb, INF); // 邊節點 -> 端點2
        adde(ss, numv++, cc); // 源點 -> 邊節點，容量=邊權
    }
}

HDU 3917 Road Constructions

題意

有向圖，每條邊屬於某公司。選公司必選其所有邊；且若選邊 u→v，則 v 的出邊所屬公司也必須選。求最大利潤。

建模思路

以公司為節點構建新圖：
- 公司節點權值 = 該公司邊的總收入 - 總成本。
- 原圖中若公司 A 的邊指向公司 B 的邊的終點，則 A 依賴 B，新圖加邊 A→B (INF)。
- 在公司圖上跑最大權閉合子圖。

關鍵代碼

for (int i = 1; i <= n; i++)
    for (int j = head2[i]; j != -1; j = e2[j][1])
        for (int vj = head2[e2[j][0]]; vj != -1; vj = e2[vj][1])
            if (e2[vj][2] != e2[j][2])
                adde(e2[j][2], e2[vj][2], INF); // 公司依賴關係

for (int i = 1; i <= m; i++) {
    if (cpy[i] > 0) { adde(ss, i, cpy[i]); sumz += cpy[i]; }
    else adde(i, tt, -cpy[i]);
}

Dinic 最大流模板（通用）

bool bfs() { /* 分層圖構建 */ }
int dfs(int u, int minf) { /* 疊加增廣 */ }
int dinic() { /* 多次 BFS+DFS */ }

總結與心得

• 最大權閉合子圖是將「選擇依賴」問題轉化為最小割的經典模型。
• 關鍵在於正確構造依賴邊（容量 INF）和節點權值到源匯邊的映射。
• HDU 3879 用「邊作節點」技巧處理「選邊必選點」；HDU 3917 用「公司作節點」抽象業務依賴。
• 數組大小需預估：3879 中節點數 = 原點數 + 邊數 + 2，邊數 = 原邊數*2 + 邊數*2 + 點數*2。