HDU 4067 Random Maze：最小費用最大流構建隨機圖

題目大意

給定一個有向圖，每條邊有兩種決策：「保留」（花費 a）或「刪除」（花費 b）。目標是以最小總花費，將圖改造為一張「隨機圖」。隨機圖需滿足：

• 有唯一入口 s 與唯一出口 t
• 入口 s：出度 = 入度 + 1
• 出口 t：入度 = 出度 + 1
• 其餘頂點：入度 = 出度

核心思路：最小費用最大流（MCMF）

本題是經典的「度數平衡」問題，可轉化為最小費用流模型：

1. 貪心預處理：對每條邊，先選擇花費較小的狀態（保留或刪除），累加基礎花費 ans。此時圖未必滿足度數條件。
2. 建立流網絡：
   • 源點 S、匯點 T
   • 對於每個頂點 i，計算 temp[i] = out[i] - in[i]（入口 s 再 -1，出口 t 再 +1）
   • temp[i] > 0：S → i 容量 temp[i]，費用 0（需流出）
   • temp[i] < 0：i → T 容量 -temp[i]，費用 0（需流入）
3. 邊的決策轉換：對原圖每條邊 u→v
   • 若初始選「保留」（a < b）：加邊 u→v 容量 1，費用 b-a（改為刪除的額外代價）
   • 若初始選「刪除」：加邊 v→u 容量 1，費用 a-b（改為保留的額外代價）
4. 求解：跑 MCMF，若最大流量等於總需求流量 totflow，則答案為 ans + cost；否則輸出 impossible。

關鍵代碼片段（SPFA 實現 MCMF）

bool spfa() {
    fill(dis, dis+T+1, INF);
    fill(vis, vis+T+1, 0);
    fill(pre, pre+T+1, -1);
    queue<int> q; q.push(S); dis[S]=0; vis[S]=1;
    while(!q.empty()){
        int u=q.front(); q.pop(); vis[u]=0;
        for(int i=head[u]; ~i; i=ed[i].next){
            if(!ed[i].w) continue;
            int v=ed[i].v;
            if(dis[v] > dis[u] + ed[i].c){
                dis[v]=dis[u]+ed[i].c; pre[v]=i;
                if(!vis[v]){ vis[v]=1; q.push(v); }
            }
        }
    }
    return dis[T]!=INF;
}

void mcmf(){
    while(spfa()){
        int tmp=INF;
        for(int i=pre[T]; ~i; i=pre[ed[i].u]) tmp=min(tmp, ed[i].w);
        for(int i=pre[T]; ~i; i=pre[ed[i].u]){
            ed[i].w -= tmp; ed[i^1].w += tmp;
            cost += tmp * ed[i].c;
        }
        flow += tmp;
    }
}

複雜度分析

• 頂點數 N ≤ 100，邊數 M ≤ 2000
• MCMF 基於 SPFA，實際運行極快，滿足時限

避坑指南

• 入口 s、出口 t 的度數修正：temp[s]--、temp[t]++
• 雙向邊建圖時，反向邊費用取負，容量為 0
• 長整型防溢出（ans、cost 可能較大）
• 多測試用例需完整重置全域變數

總結

本題巧妙地將「最小化修改代價」轉化為「在滿足度數約束下的最小費用流」。關鍵洞見：先貪心鎖定基礎狀態，再用流網絡建模「翻轉決策」的代價與度數平衡需求。這是網絡流建模能力的優秀練習題。