Codeforces 302D Destroying Roads：最短路枚舉公共路段最大化刪除邊數

問題重述

無向無權連通圖 n ≤ 3000, m ≤ n(n-1)/2。需保留邊使得：
dist(s1, t1) ≤ l1 且 dist(s2, t2) ≤ l2。
求**最多可刪除邊數**（即保留最少邊數）。

核心觀察

保留的邊集 = 兩條路徑的並集。為使並集最小，兩路徑應**盡可能共用邊**。共用部分必為一段**最短路**（否則可替換為更短段進一步縮小並集）。

算法流程

1. 對每個點跑 BFS，得 d[u][v]（全點對最短路），O(n(n+m)) 可接受（稀疏圖約 2.7×10⁷ 操作）。
2. 若 d[s1][t1] > l1 或 d[s2][t2] > l2 → 輸出 -1。
3. 初始答案 ans = d[s1][t1] + d[s2][t2]（無共用邊）。
4. 枚舉共用路段端點 i, j (1≤i≤j≤n)，考慮兩種方向：
   w1 = min(d[s1][i]+d[i][j]+d[j][t1], d[s1][j]+d[j][i]+d[i][t1])
w2 = min(d[s2][i]+d[i][j]+d[j][t2], d[s2][j]+d[j][i]+d[i][t2])
   若 w1 ≤ l1 && w2 ≤ l2，則 ans = min(ans, w1 + w2 - d[i][j])（扣除重複段）。
5. 最終保留邊數 = ans，可刪除 = m - ans。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 3005;

int n, m;
vector G[MAXN];
int d[MAXN][MAXN];

void bfs(int s) {
    fill(d[s]+1, d[s]+n+1, INF);
    queue q; q.push(s); d[s][s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : G[u]) if (d[s][v] == INF) {
            d[s][v] = d[s][u] + 1;
            q.push(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m) {
        for (int i = 1; i <= n; ++i) G[i].clear();
        for (int i = 0; i < m; ++i) {
            int u, v; cin >> u >> v;
            G[u].push_back(v); G[v].push_back(u);
        }
        for (int i = 1; i <= n; ++i) bfs(i);

        int s1, t1, l1, s2, t2, l2;
        cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;

        if (d[s1][t1] > l1 || d[s2][t2] > l2) {
            cout << -1 << "\n";
            continue;
        }

        int ans = d[s1][t1] + d[s2][t2];
        for (int i = 1; i <= n; ++i) {
            for (int j = i; j <= n; ++j) {
                int w1 = min(d[s1][i] + d[i][j] + d[j][t1],
                             d[s1][j] + d[j][i] + d[i][t1]);
                int w2 = min(d[s2][i] + d[i][j] + d[j][t2],
                             d[s2][j] + d[j][i] + d[i][t2]);
                if (w1 > l1 || w2 > l2) continue;
                ans = min(ans, w1 + w2 - d[i][j]);
            }
        }
        cout << m - ans << "\n";
    }
    return 0;
}

複雜度與細節

• 時間：O(n(n+m) + n²)，n=3000 約 3×10⁷，2s 內輕鬆通過。
• 空間：d[][] 約 36 MB（int[3001][3001]），符合 256 MB 限制。
• 枚舉 i ≤ j 利用對稱性減半常數。