HDU 2686 Matrix：最大費用流解矩陣往返路徑最大和

題目大意

n×n 矩陣，每格有正整數權值。從左上角 (0,0) 走到右下角 (n-1,n-1)（只能右/下），再原路返回（只能左/上），起終點可重複，其餘格子不可重複。求經過格子權值和最大值。

關鍵轉化

往返且不重複（除首尾） ⇔ 找兩條不相交（除首尾）的從 (0,0) 到 (n-1,n-1) 的路徑，權值和最大。即最大費用最大流，流量 = 2。

建圖模型

1. 拆點：每個格子 (i,j) 拆為 in 和 out 兩個節點，連邊 in→out，容量 1，費用 = 格子權值（首尾容量 2）。
2. 鄰接連邊：out→鄰居in（右/下），容量 1，費用 0。
3. 源匯：源點連 (0,0)_in，容量 2，費用 0；(n-1,n-1)_out 連匯點，容量 2，費用 0。

算法：SPFA 求最大費用增廣路（MCMF）

因費用為正，求最大費用流，SPFA 中距離取最大值（或費用取負求最小費用流）。流量增廣至 2 即可。

完整代碼（C++，ISAP/SPFA 混合）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010, MAXM = 1001000, INF = 1<<30;
struct Edge { int to, nxt, cap, cost, flow; } e[MAXM];
int h[MAXN], ec, S, T, N;
int dis[MAXN], pre[MAXN], cur[MAXN];
bool inq[MAXN];

void init() { fill(h, h+N, -1); ec = 0; }
void addEdge(int u, int v, int cap, int cost) {
    e[ec] = {v, h[u], cap, cost, 0}; h[u] = ec++;
    e[ec] = {u, h[v], 0, -cost, 0}; h[v] = ec++;
}
bool spfa() {
    fill(dis, dis+N, -INF); fill(inq, inq+N, false);
    dis[S] = 0; queue q; q.push(S); inq[S] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = h[u]; ~i; i = e[i].nxt) {
            Edge &ed = e[i];
            if (ed.cap > ed.flow && dis[ed.to] < dis[u] + ed.cost) {
                dis[ed.to] = dis[u] + ed.cost;
                pre[ed.to] = i;
                if (!inq[ed.to]) { inq[ed.to] = true; q.push(ed.to); }
            }
        }
    }
    return dis[T] > -INF;
}
int maxCostMaxFlow() {
    int cost = 0, flow = 0;
    while (flow < 2 && spfa()) {
        int f = 2 - flow;
        for (int v = T; v != S; v = e[pre[v]^1].to)
            f = min(f, e[pre[v]].cap - e[pre[v]].flow);
        for (int v = T; v != S; v = e[pre[v]^1].to) {
            e[pre[v]].flow += f;
            e[pre[v]^1].flow -= f;
            cost += f * e[pre[v]].cost;
        }
        flow += f;
    }
    return cost;
}
int main() {
    int n;
    while (cin >> n) {
        vector> a(n, vector(n));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> a[i][j];
        N = n * n * 2 + 2;
        S = n*n*2; T = S+1;
        init();
        auto id_in = [&](int x, int y){ return (x*n+y)*2; };
        auto id_out = [&](int x, int y){ return (x*n+y)*2+1; };
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int cap = (i==0&&j==0) || (i==n-1&&j==n-1) ? 2 : 1;
                addEdge(id_in(i,j), id_out(i,j), cap, a[i][j]);
                if (i+1 < n) addEdge(id_out(i,j), id_in(i+1,j), 1, 0);
                if (j+1 < n) addEdge(id_out(i,j), id_in(i,j+1), 1, 0);
            }
        }
        addEdge(S, id_in(0,0), 2, 0);
        addEdge(id_out(n-1,n-1), T, 2, 0);
        cout << maxCostMaxFlow() << '\n';
    }
    return 0;
}

複雜度

• 節點數 2n²+2 ≤ 1802，邊數 ≈ 4n²。
• SPFA 兩次增廣，實際極快。

關鍵點

1. 拆點限制每格最多經過一次（首尾除外）。
2. 最大費用流模板需熟練（SPFA 求最長路）。
3. 費用為正，直接求最大費用；若模板只支援最小費用，費用取負即可。