HDU 4862 Jump：最小 K 路徑覆蓋 + 費用流建模詳解

題目大意

N×M 矩陣，每格數字 0~9。從任意格開始，每步只能向正下或正右跳任意步數。跳躍代價 = 曼哈頓距離 - 1。若起跳格與落地格數字相同，獲得該數字的能量。每格最多經過一次。最多選 K 個起點。問能否覆蓋所有格，若能求最大淨能量（獲得 - 代價）。

建模：最小 K 路徑覆蓋 → 最小費用最大流

二部圖構造

• 左部 X：N×M 個節點，代表「作為跳躍起點」
• 右部 Y：N×M 個節點，代表「作為跳躍終點」
• 源點 S，匯點 T

邊構造

1. S → X_i：容量 1，費用 0（每格最多作為一次起點）
2. Y_i → T：容量 1，費用 0（每格最多作為一次終點）
3. X_u → Y_v：若 u 能一步跳到 v（同行右側或同列下方），容量 1，費用 = 跳躍代價 - 獲得能量 = (dist-1) - (same? digit:0)
4. 關鍵：額外節點 X_extra：S → X_extra 容量 K，費用 0；X_extra → Y_i 容量 1，費用 0。表示「從虛擬起點直接開始，不消耗跳躍代價，最多 K 次」。

為什麼這樣建模正確？

• 每條 X_u → Y_v 流量 1 代表一步跳躍 u→v。
• 流經 X_extra → Y_i 代表 i 作為某條路徑的起點（無前驅）。
• 流經 X_u → Y_v 代表 v 由 u 到達（有前驅）。
• 每個 Y_i 入流量 ≤ 1 保證每格最多被到達一次（即最多經過一次）。
• S → X_extra 容量 K 限制起點數 ≤ K。
• 滿流（總流量 = N×M）⇔ 所有格被覆蓋。最小費用 ⇔ 最大淨能量（取負）。

最小費用最大流實現（SPFA + 滾動數組）

struct MCMF {
    struct Edge { int to, cap, cost, rev; };
    int N; vector<vector<Edge>> G;
    MCMF(int n): N(n), G(n) {}
    void addEdge(int u,int v,int cap,int cost){
        G[u].push_back({v,cap,cost,(int)G[v].size()});
        G[v].push_back({u,0,-cost,(int)G[u].size()-1});
    }
    pair<int,int> minCostMaxFlow(int s,int t){
        int flow=0, cost=0;
        vector<int> dist(N), pv(N), pe(N);
        while(true){
            fill(dist.begin(), dist.end(), INF);
            vector<bool> inq(N);
            dist[s]=0; queue<int> q; q.push(s); inq[s]=true;
            while(!q.empty()){
                int u=q.front(); q.pop(); inq[u]=false;
                for(int i=0;i0 && dist[e.to] > dist[u]+e.cost){
                        dist[e.to]=dist[u]+e.cost;
                        pv[e.to]=u; pe[e.to]=i;
                        if(!inq[e.to]){ q.push(e.to); inq[e.to]=true; }
                    }
                }
            }
            if(dist[t]==INF) break;
            int add=INF;
            for(int v=t;v!=s;v=pv[v]) add=min(add,G[pv[v]][pe[v]].cap);
            for(int v=t;v!=s;v=pv[v]){
                Edge &e=G[pv[v]][pe[v]];
                e.cap-=add; G[v][e.rev].cap+=add;
                cost+=add*e.cost;
            }
            flow+=add;
        }
        return {flow,cost};
    }
};

完整建模代碼片段

int n=M*N;
int S = 2*n, T = 2*n+1, EXTRA = 2*n+2;
MCMF mcmf(2*n+3);

for(int i=0;i X_i
    mcmf.addEdge(n+i, T, 1, 0);         // Y_i -> T
    mcmf.addEdge(EXTRA, n+i, 1, 0);     // X_extra -> Y_i
}
mcmf.addEdge(S, EXTRA, K, 0);           // S -> X_extra (cap=K)

for(int r=0;r

複雜度與優化

  
節點數 V = 2NM+3 ≤ 2×15×15+3 = 453
  
邊數 E ≈ NM×(N+M) ≤ 15×15×30 = 6750
  
SPFA 平均 O(kE)，實際極快
  
可用 Dijkstra + 條件優化（費用無負環）更穩健


關鍵點總結

  
最小 K 路徑覆蓋 = 二部圖 + 虛擬起點節點（容量 K）
  
費用 = 代價 - 收益，最小費用流 = 最大淨收益
  
每格拆分為 X（出）和 Y（入）強制顧點不重複
  
滿流判定覆蓋可行性