HDU 2686 Matrix 最大費用最大流 雙路徑不重疊

問題建模

N×N 網格（N<30），每格有權值。從左上角 (1,1) 走到右下角 (N,N) 再返回，去程只能右/下，回程只能左/上，除起終點外不可重複經過同一格。最大化路徑權值和。

關鍵轉化：雙路徑 = 兩條不相交路徑

去程 + 回程 等價於 從源點到匯點的兩條節點不相交路徑（起終點可共用）。標準最大費用最大流模型。

網絡構建

1. 節點拆分：每格 (i,j) 拆為 in 和 out，連邊 in→out，容量 1，費用 = 格子權值
2. 超級源點 S, 匯點 T：
   • S → (1,1)_in，容量 2，費用 0
   • (N,N)_out → T，容量 2，費用 0
3. 網格邊：
   • (i,j)_out → (i,j+1)_in，容量 1，費用 0（右）
   • (i,j)_out → (i+1,j)_in，容量 1，費用 0（下）

SPFA 求最大費用流

因費用非負，求最大費用可將費用取反求最小費用，或直接在 SPFA 中用 dis[v] < dis[u] + cost 放寬條件。

代碼框架

struct Edge { int to, nxt, cap, cost; };
vector<Edge> edges;
vector<int> head;

void addEdge(int u, int v, int cap, int cost) {
    edges.push_back({v, head[u], cap, cost});
    head[u] = edges.size()-1;
    edges.push_back({u, head[v], 0, -cost});
    head[v] = edges.size()-1;
}

bool spfa(int s, int t, vector<int>& dist, vector<int>& pre) {
    // 標準 SPFA 求最長路（費用為正時）
    // 返回是否存在增廣路
}

int maxCostMaxFlow(int s, int t, int maxFlow) {
    int flow = 0, cost = 0;
    while (flow < maxFlow && spfa(s, t, dist, pre)) {
        int f = maxFlow - flow;
        for (int v = t; v != s; v = edges[pre[v]^1].to)
            f = min(f, edges[pre[v]].cap);
        for (int v = t; v != s; v = edges[pre[v]^1].to) {
            edges[pre[v]].cap -= f;
            edges[pre[v]^1].cap += f;
            cost += edges[pre[v]].cost * f;
        }
        flow += f;
    }
    return cost;
}

答案計算

流量固定為 2。最終答案 = maxCost + val[1][1] + val[N][N]（起終點權值被拆分邊計算了兩次，需補回一次）。

複雜度

• 節點數 ~ 2×N² ≤ 1800，邊數 ~ 4×N² ≤ 3600
• SPFA 兩次增廣，極快