攜程復賽題：最短路徑邊刪除代價最小割 + SAP 最大流

問題描述

給定圖，求從 s 到 t 的最短路徑集合。需刪除一些邊使所有最短路被切斷，刪除代價為邊權 c，求最小總代價。等價於：在最短路子圖中求 s-t 最小割 = 最大流。

解法步驟

1. Dijkstra 從 s 計算 dis[u] = 最短距離
2. 反向 BFS 從 t 找所有在最短路上的邊：dis[u] + w == dis[v]
3. 構建流網絡：最短路邊容量 = c，其餘邊容量 = 0
4. SAP (ISAP) 最大流求最小割值

關鍵資料結構

• 鄰接表存圖與流網絡
• SAP：gap、dis、cur 當前弧優化
• 數據範圍陷阱：m ≤ 11000（題目說 10000 實際更大）

核心程式碼片段

// Dijkstra + 反向 BFS 找最短路邊
// 建流圖：G.add(u, v, c) // 容量為 c
// SAP 最大流
int sap(int s, int t, int n) { ... } // 標準 ISAP 實作

完整程式碼結構

struct Graph { // 原圖
    struct Edge { int u,v,w,c,next; } e[MAXM];
    int head[MAXN];
    void add(int u,int v,int w,int c) { ... }
} gs;

struct MaxFlow { // 流網絡
    struct Edge { int u,v,w,next; } e[MAXM];
    int head[MAXN], dis[MAXN], cur[MAXN], gap[MAXN], pre[MAXN], aug[MAXN];
    void add(int u,int v,int w) { ... } // 残量網絡雙向邊
    int sap(int s,int t,int n) { ... } // ISAP 主流程
} G;

int main() {
    while (scanf("%d%d",&n,&m), n||m) {
        gs.init(); scanf("%d%d",&st,&ed);
        for (i=1;i<=m;i++) { scanf("%d%d%d%d",&a,&b,&w,&c); gs.add(a,b,w,c); gs.add(b,a,w,c); }
        G.init(MAXN-1);
        printf("%d\n", dijkstra_sap(st,ed,n));
    }
}