HDU 5294：最短路 + 最大流解古墓通道切斷問題

問題描述

給定無向圖 N 個節點、M 條邊（邊長 l_i）。起點 1，終點 N。僅允許走最短路徑。敵方可切斷邊。問：

1. 最少切斷幾條邊使最短路不通？（最小割）
2. 最多切斷幾條邊仍保留至少一條最短路？（M - 最短路邊數）

解題思路

1. 雙向 SPFA/Dijkstra：從起點跑 dis1[]，從終點跑 dis2[]。最短路長度 minDist = dis1[N]。
2. 篩選最短路邊：對每條無向邊 (u, v, w)，若 dis1[u] + w + dis2[v] == minDist 或 dis1[v] + w + dis2[u] == minDist，則該定向邊屬於最短路圖。構建有向圖（按距離從小到大定向）。
3. 最大流 = 最小割：在最短路有向圖上，源點 1，匯點 N，容量均為 1，跑 Dinic 最大流，即為答案 1。
4. 答案 2：M - (最短路DAG中的邊數)。因為只能保留最短路邊，其餘皆可切。

關鍵代碼片段

// SPFA 求最短路
void spfa(int s, int n, int *dis) { ... }

// Dinic 最大流
struct Edge { int to, cap, next; };
void addEdge(int u, int v, int c) { ... }
bool bfs() { ... }
int dfs(int u, int flow) { ... }
int dinic() { ... }

int main() {
    while (~scanf("%d%d", &n, &m)) {
        // 讀邊、建圖、跑雙向 SPFA
        // 篩選最短路邊構建流網絡
        int ans1 = dinic();
        int ans2 = m - (minDist_edge_count); // 注意：最短路DAG邊數
        printf("%d %d\n", ans1, ans2);
    }
}

複雜度

• SPFA：O(k * M) 平均較快，N ≤ 2000, M ≤ 60000。
• Dinic：最短路 DAG 邊數 ≤ M，層數 ≤ N，O(E * sqrt(V)) 實際極快。