HDU 5093 Battle ships：二分圖最大匹配

題目

m×n 地圖，* 海、o 浮冰、# 冰山。戰艦只能放 *，且同行/列不得有兩艦，除非中間有 # 隔開。求最多放幾艦。

建圖

1. 行分段：每行按 # 分割，每段賦予唯一 ID rowId。
2. 列分段：同理得 colId。
3. 每個 * 格連接其 rowId 和 colId。選擇該格即佔用該行段與列段。

問題轉化為二分圖最大匹配（行段左部，列段右部）。

匈牙利/DFS 匹配

vector G[MAXN];
int match[MAXN];
bool vis[MAXN];
bool dfs(int u) {
    for (int v : G[u]) if (!vis[v]) {
        vis[v]=1;
        if (match[v]==-1 || dfs(match[v])) {
            match[v]=u; return true;
        }
    }
    return false;
}
int maxMatch() {
    int ans=0;
    fill(match, match+R+1, -1);
    for (int u=1; u<=L; ++u) {
        fill(vis, vis+R+1, 0);
        if (dfs(u)) ++ans;
    }
    return ans;
}

複雜度

點數 ≤ 2500，邊數 ≤ 2500，DFS 匹配 O(VE) 極快。