6.5 拆铁路

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

小\(X\)同学最近在玩一款造桥游戏。游戏由\(N\)个岛屿组成，岛屿 1 为首都，岛屿之间已有\(M\)条公路和\(K\)座桥相连（公路与桥均为双向），使得\(N\)个岛屿互相可达，每座桥都直接连接首都与某个岛屿\(s\)。但小\(X\)同学为了节省经费（中饱私囊）决定拆除一些桥，但保证任意岛屿到首都的最短路距离不变。小\(X\)同学想知道最多能拆掉多少座桥。

数据输入

输入的第一行为包括三个整数\(n\ (2\leq n\leq 10^4),\ m\ (1\leq m\leq 2\times 10^4),\ k\ (1\leq k\leq 10^4)\)分别表示岛屿数，公路数与桥的数量。接下来\(m\)行，每行三个整数\(u_i,\ v_i,\ x_i\ (1\leq u_i,\ v_i\leq n;\ u_i\neq v_i;\ 1\leq x_i\leq 10^9)\) 表示第\(i\)条公路连接\(u_i\)岛屿与\(v_i\)岛屿，长为\(x_i\)。接下来\(k\)行，每行两个整数\(s_i, y_i\ (2\leq s_i\leq n;\ 1\leq y_i\leq 10^9)\)表示第\(i\)座桥连接首都与\(s_i\)岛屿，长度为\(y_i\)。

数据输出

输出一个整数表示最多可拆除多少座桥，使得首都到其他任意岛屿的最短路不变。

输入示例 输出示例
5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5		 2
2 2 3
1 2 2
2 1 3
2 1
2 2
2 3		 2

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <queue>
using namespace std;
typedef __int64 ll;
#define fi first
#define se second
#define mp make_pair
const int N = 10007;
const int M = 20007;
int et, head[N], brid[N];
ll dis[N];
bool vis[N], used[N];
struct Edge {
    int v, w, nxt;
    Edge() {}
    Edge(int _v, int _w, int _nxt) {
        v = _v, w = _w, nxt = _nxt;
    }
} e[M << 1];
void addEdge(int u, int v, int w) {
    e[et] = Edge(v, w, head[u]), head[u] = et++;
    e[et] = Edge(u, w, head[v]), head[v] = et++;
}
void bfs(int n) {
    int i;
    for (i = 1; i <= n;++i) dis[i] = 1e17,
        vis[i] = used[i] = false;
    priority_queue<pair<pair<ll, int>, int> > que;
    que.push(mp(mp(0, 0), 1));
    for (i = 1; i <= n;++i)
        if (~brid[i])
            que.push(mp(mp(-brid[i], -i), i));
    while (!que.empty()) {
        ll D = -que.top().fi.fi;
        int src = -que.top().fi.se;
        int u = que.top().se;
        que.pop();
        if (vis[u]) continue;
        vis[u] = true, used[src] = true, dis[u] = D;
        for (int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                que.push(mp(mp(-dis[v], -src), v));
            }
        }
    }
}
int main() {
    int n, m, k, i;
    scanf("%d%d%d", &n, &m, &k);
    et = 0, memset(head + 1, -1, sizeof(*head) * n);
    for (i = 0; i < m;++i){
        int _ui, _vi, _xi;
        scanf("%d%d%d", &_ui, &_vi, &_xi);
        addEdge(_ui, _vi, _xi);
    }
    memset(brid + 1, -1, sizeof(*brid) * n);
    for (i = 0; i < k;++i){
        int _si, _yi;
        scanf("%d%d", &_si, &_yi);
        if (brid[_si] == -1 || brid[_si] > _yi)
            brid[_si] = _yi;
    }
    bfs(n);
    int ans = k;
    for (i = 1; i <= n;++i)
        if (~brid[i] && used[i])
            --ans;
    printf("%d", ans);
    return 0;
}

设计思路与复杂度分析

如果在不使用桥的情况下，首都到岛屿\(i\)为最短距离，则敲\(1\leftrightarrow i\)不需要使用（如果存在）。但是使用一条桥可能会更新多个点的距离，所以不能通过先先处理路再处理桥的方法。

暴力做法：每次去掉一座桥，计算首都1到其它节点的最短距离，如果存在一个节点不是最短距离，说明此桥不可去除，复杂度\(O(knlogn)\)。

对于一座桥是否使用，主要取决于使用其它桥和公路的情况下的距离是否会比该桥的距离短。这可以看成一个竞争过程，谁先到达\(i\)谁就占据改点。于是可以使用Dijkstra算法：每次去除距离最短且未访问过的点进行邻近的点的距离更新。处理过程中需要积累每个点由谁占据，用来判断最后使用了那些桥。如此复杂度即为Dij算法的复杂度\(O(nlogn)\)。

0%