算法

(最短路) $O(n^2)$

首先，将“删去的道路最多”转换为“留下的道路最少”
然后，再考虑只有 $s_1$ 而没有 $s_2$ 的情况怎么求出答案，不难想到其实就是求出从起点到 $s_1$ 的最短路就行了，求出来距离的就代表了“最少留下的道路个数”
那如果吧 $s_2$ 也考虑进来呢？我们可以把从起点到 $s_1$ 和 $s_2$ 的过程反过来考虑：有两个人分别从 $s_1$ 和 $s_2$ 出发，一同前往点 $1$
于是，我们很容易想到一个贪心的策略：两个人一定是先各自走自己的路，然后再在某一点汇合后一起走同一条路（之后就不分开了）到达点 $1$。
为什么呢？因为如果有机会的话，其中一个人完全可以主动和另一个人走同一条路而避免自己走额外的路造成浪费。

至此，枚举汇合点 $x$，那么“最少能留下来的边”就是“$x$ 到起点的最短路” $+$ “$x$ 到 $s_1$ 的最短路” $+$ “$x$ 到 $s_2$ 的最短路”，拿 $m$ 减去这个值得到的就是“最多能删去的道路”，对所有汇合点的情况求一个最大值即可。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> to(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }

    const int INF = 1001001001;
    auto bfs = [&](int sv) {
        vector<int> dist(n, INF);
        queue<int> q;
        dist[sv] = 0; q.push(sv);
        while (q.size()) {
            int v = q.front(); q.pop();
            for (int u : to[v]) {
                if (dist[u] != INF) continue;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
        return dist;
    };

    int s1, t1, s2, t2;
    cin >> s1 >> t1 >> s2 >> t2;
    --s1; --s2; 

    int ans = -1;
    rep(sv, n) {
        auto d = bfs(sv);
        if (d[0] == INF or d[s1] == INF or d[s2] == INF) continue;
        if (d[0]+d[s1] > t1 or d[0]+d[s2] > t2) continue;
        ans = max(ans, m-(d[0]+d[s1]+d[s2]));
    }

    cout << ans << '\n';

    return 0;
}