HDU 4370 0 or 1：矩陣轉圖求最短路

問題轉化

n×n 矩陣 C，找 0/1 矩陣 X 滿足：
(1) 第一行和 = 1；(2) 最後一列和 = 1；(3) 中間行列和相等。
最小化 Σ C_ijX_ij。

圖論建模

• 條件 (1) → 節點 1 出度 1。
• 條件 (2) → 節點 n 入度 1。
• 條件 (3) → 節點 2…n−1 入度 = 出度。

即尋找從 1 到 n 的一條路徑（邊權 C），或 1 和 n 各自有一個環（不相交）。
答案 = min(最短路 1→n, 1 的最小環 + n 的最小環)。

SPFA 求最短路與最小環

int spfa(int s, int n, const vector>& G, vector& dist) {
    fill(dist.begin(), dist.end(), INF);
    queue q; vector inq(n+1);
    dist[s] = 0; q.push(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (auto [v, w] : G[u])
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) { q.push(v); inq[v] = true; }
            }
    }
    return dist[n];
}
int minCycle(int s, int n, const vector>& G) {
    vector dist(n+1, INF);
    queue q; vector inq(n+1);
    for (auto [v, w] : G[s]) { dist[v] = w; q.push(v); inq[v] = true; }
    while (!q.empty()) { ... }
    return dist[s]; // 回到 s 的最短距離
}

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    while (cin >> n) {
        vector>> G(n+1);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                int c; cin >> c;
                G[i].push_back({j, c});
            }
        vector dist(n+1);
        int sp = spfa(1, n, G, dist);
        int c1 = minCycle(1, n, G);
        int cn = minCycle(n, n, G);
        cout << min(sp, c1 + cn) << '\n';
    }
    return 0;
}

複雜度

SPFA 平均 O(E)，E = n² ≤ 9×10⁴，極快。