您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 2594 二分圖最小路徑覆蓋：Floyd + 最大流解法

編輯：關於C++

題目大意

給定一個有向圖，求覆蓋所有頂點所需的最少路徑數。每個頂點可重複訪問，路徑可從任意點開始、結束。

核心轉化：最小路徑覆蓋 = |V| - 最大匹配數

將原圖轉化為二分圖：每個頂點 u 拆分為左部 u_in 和右部 u_out。若原圖有邊 u → v，則在二分圖添加邊 u_in → v_out。二分圖的最大匹配數即為可合併的路徑段數，最小路徑覆蓋 = 總頂點數 - 最大匹配數。

為什麼只連單向邊？

路徑 1→2→3 對應匹配 1_in-2_out、2_in-3_out。頂點 2 在左部用一次（作為 1 的後繼），右部用一次（作為 3 的前驅），恰好滿足路徑連接條件。若連雙向邊會導致過度匹配。

處理可重複訪問：Floyd 传遞閉包

題目允許頂點重複訪問，即若 u 可達 v 則視為有邊。先用 Floyd 算法計算所有點對最短路徑/可達性，再根據可達性構建二分圖邊。

完整代碼實現

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;

struct Edge {
    int to, cap, rev;
    Edge(int a, int b, int c) : to(a), cap(b), rev(c) {}
};

vector<Edge> G[MAXN];
int level[MAXN], iter[MAXN];

void addEdge(int from, int to, int cap) {
    G[from].push_back(Edge(to, cap, G[to].size()));
    G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0; q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto &e : G[v]) {
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < G[v].size(); ++i) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int maxFlow(int s, int t) {
    int flow = 0;
    while (true) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
}

int dist[510][510];

void floyd(int V) {
    for (int k = 1; k <= V; ++k)
        for (int i = 1; i <= V; ++i)
            for (int j = 1; j <= V; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main() {
    int n, m, a, b;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        
        // 初始化距離矩陣
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = (i == j) ? 0 : INF;
        
        // 讀取邊
        for (int i = 0; i < m; ++i) {
            cin >> a >> b;
            dist[a][b] = 1;
        }
        
        // Floyd 計算可達性
        floyd(n);
        
        // 構建二分圖網絡流
        int S = 0, T = 2 * n + 1;
        for (int i = 0; i <= T; ++i) G[i].clear();
        
        for (int i = 1; i <= n; ++i) {
            addEdge(S, i, 1);           // 源點連左部
            addEdge(n + i, T, 1);       // 右部連匯點
        }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (dist[i][j] < INF && i != j)
                    addEdge(i, n + j, 1);  // 可達則連邊
        
        int matching = maxFlow(S, T);
        cout << n - matching << endl;  // 最小路徑覆蓋
    }
    return 0;
}