HDU 3035 War - 平面圖最小割轉最短路經典模型

HDU 3035 War：平面圖最小割問題的對偶圖最短路解法

給定一個網格狀平面圖，包含水平、垂直及斜向邊，每條邊有摧毀代價。求阻斷源點 S 到匯點 T 連通性的最小總代價（最小割）。

核心洞察：平面圖最小割 = 對偶圖最短路

• 將平面圖的每個面（包含外部無限面）視為對偶圖中的一個節點
• 原圖中相鄰兩面共用的邊，在對偶圖中連接對應節點，權重為原邊代價
• S-T 最小割對應對偶圖中「外部面」到「內部面」的最短路徑
• 因所有邊權非負，可用 Dijkstra 算法求解

圖構建技巧：四層節點編碼

將 N×M 網格的每個格子拆分為 4 個三角形面（左上、右上、左下、右下），編碼如下：

// 節點編碼：每個格子 4 個面，共 n*m*4 個節點
// 額外添加源點 s = n*m*4，匯點 t = n*m*4+1

// 讀入水平邊 (n+1) 行，每行 m 條
// 讀入垂直邊 n 行，每行 (m+1) 條
// 讀入斜向邊：每個格子 4 條（兩條主對角線方向）

具體連邊邏輯處理邊界條件：最上行連 T，最下行連 S，最左列連 S，最右列連 T，內部面之間雙向連邊。

Dijkstra 實現要點

struct Dijkstra {
    struct Edge { int u, v, dist; };
    struct HeapNode { int d, u; bool operator<(const HeapNode& o) const { return d > o.d; } };
    
    vector edges;
    vector head, nxt;
    vector dist;
    vector done;
    
    void init(int n) { /* 初始化 */ }
    void addEdge(int u, int v, int w) { /* 添加雙向邊 */ }
    
    int dijkstra(int s, int t) {
        priority_queue pq;
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0; pq.push({0, s});
        while (!pq.empty()) {
            int u = pq.top().u; pq.pop();
            if (done[u]) continue; done[u] = true;
            for (int i = head[u]; ~i; i = nxt[i]) {
                Edge &e = edges[i];
                if (dist[e.v] > dist[u] + e.dist) {
                    dist[e.v] = dist[u] + e.dist;
                    pq.push({dist[e.v], e.v});
                }
            }
        }
        return dist[t];
    }
};

複雜度與優勢

• 節點數：O(NM)，邊數：O(NM)
• Dijkstra：O(NM log NM)，遠優於直接在原圖跑最大流（Dinic O(V²E) 會 TLE）
• 利用平面圖特性將最小割轉化為最短路，是經典必會技巧

此題是平面圖最小割轉對偶圖最短路的教科書級範例，掌握節點編碼與邊構建細節對解決同類問題至關重要。