HDU 5093 停船問題：冰山隔離下的最大流 / 二分圖建模

問題描述

給定 m 行 n 列矩陣：# 為冰山，* 為大海，o 為浮冰。船隻只能停在大海 * 上，且同一行/列最多停一艘，但若中間有冰山 # 隔離，則該行/列可視為多個獨立段落，各自最多停一艘。求最多能停多少艘船。

建模思路

經典「放置不相互攻擊的棋子」問題變體。將每個連續海段視為一個節點：

• 行段：同一行中被 # 分隔的連續 * 區間。
• 列段：同一列中被 # 分隔的連續 * 區間。
• 每個 * 位置屬於唯一的一個行段和一個列段，在二分圖中連一條邊（容量 1）。
• 源點連所有行段，所有列段連匯點，容量均為 1。最大流即為最大匹配數 = 最多停船數。

代碼實現要點

• 先掃描每行，記錄冰山位置作為分隔點，編號行段並建邊源點→行段。
• 再掃描每列，同理編號列段並建邊列段→匯點。
• 遍歷矩陣，對每個 * 連接其所屬行段與列段。
• Dinic 算法求最大流。

參考代碼片段

// 行段建圖
for (int i = 1; i <= m; i++) {
    int k = 0; num[i][k++] = 0;
    for (int j = 1; j <= n; j++)
        if (str[i][j] == '#') num[i][k++] = j;
    num[i][k++] = n+1; cnt[i] = k;
}
int k = 1;
for (int i = 1; i <= m; i++)
    for (int j = 1; j < cnt[i]; j++) {
        add_edge(0, k, 1);
        for (int l = num[i][j-1]+1; l < num[i][j]; l++)
            if (str[i][l] == '*') add_edge(k, 3000+(i-1)*n+l, 1);
        k++;
    }
// 列段建圖類似...
// 最後 max_flow(0, 8050) 即答案

作者註：雖用最大流模板通過，但二分圖建模才是正規解法；代碼建邊較繁瑣，僅供參考。