【无标题】-EW帮帮网

P5683 [CSP-J2019 江西] 道路拆除

题目描述

A 国有 $n$ 座城市，从 $\sim n$ 编号。 $1$ 号城市是 A 国的首都。城市间由 $m$ 条双向道路连通，通过每一条道路所花费的时间均为 $1$ 单位时间。

现在 A 国打算拆除一些不实用的道路以减小维护的开支，但 A 国也需要保证主要线路不受影响。因此 A 国希望道路拆除完毕后，利用剩余未被拆除的道路，从 A 国首都出发，能到达 $s_1$ 号与 $s_2$ 号城市，且所要花费的最短时间分别不超过 $t_1$ 与 $t_2$ （注意这是两个独立的条件，互相之间没有关联，即不需要先到 $s_1$ 再到 $s_2$ ）。

A 国想请你帮他们算算，在满足上述条件的情况下，他们最多能拆除多少条道路。若上述条件永远无法满足，则输出 $- 1$ 。

输入格式

第一行两个正整数 $n, m$ ，表示城市数与道路数。

接下来 $m$ 行，每行两个正整数 $x, y$ ，表示一条连接 $x$ 号点与 $y$ 号点的道路。

最后一行四个整数，分别为 $s_1,t_1,s_2,t_2$ 。

输出格式

仅一行一个整数，表示答案。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

-1

说明/提示

【数据范围】
对于 $30%30\%$ 的数据， $\le 15$ ；
另有 $20%20\%$ 的数据， $\le 100$ ， $m = n - 1$ ；
另有 $30%30\%$ 的数据， $s_1 = s_2$ ；
对于 $100%100\%$ 的数据， $\le n,m \le 3000$ ， $1≤x,y≤n1\le x,y \le n$ ， $\le s_1,s_2 \le n$ ， $\le t_1,t_2 \le n$ 。

【样例 $1$ 解释】
拆除 $(1, 2), (2, 3), (3, 4)$ 三条边。
注意：不需要令首都与除了 $s_1,s_2$ 外的点在拆除之后依然连通。

【样例 $2$ 解释】
即使一条边都不拆除，首都到 $3$ 号点的最短时间也都达到了 $2$ 单位时间。

testdata by @DYH060310

对于这题，若是直接考虑题目的要求，可以发现是非常难的。可以反过来，考虑寻找满足条件的最少边数。我们希望同时满足两个条件，故对于这两条路径的公共路径应尽量不动，可以先求出1、s1、s2三个点的单源最短路，随后枚举从1到s1、s2的中间结点，由于权值为1，则路径长度等同于边的数量。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

vector<int> bfs(int s, int n, const vector<vector<int>>& adj) {
    vector<int> dist(n + 1, INF);
    queue<int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int s1, t1, s2, t2;
    cin >> s1 >> t1 >> s2 >> t2;
    vector<int> dist1 = bfs(1, n, adj);
    vector<int> dist_s1 = bfs(s1, n, adj);
    vector<int> dist_s2 = bfs(s2, n, adj);
    if (dist1[s1] > t1 || dist1[s2] > t2) {
        cout << -1 << endl;
        return 0;
    }
    int ans = INF;

    for (int i = 1; i <= n; ++i) {
        if (dist1[i] == INF || dist_s1[i] == INF || dist_s2[i] == INF) {
            continue;
        }

        long long path1_len = (long long)dist1[i] + dist_s1[i];
        long long path2_len = (long long)dist1[i] + dist_s2[i];
        if (path1_len <= t1 && path2_len <= t2) {
            int current_edges = dist1[i] + dist_s1[i] + dist_s2[i];
            ans = min(ans, current_edges);
        }
    }
    cout << m - ans;
    return 0;
}

【无标题】