最短路生成树学习笔记

更好的阅读体验戳此进入

写在前面

做 ABC 的时候碰到了一道题，用到的算法是最短路生成树。感觉这个似乎是个挺冷门的算法，OI Wiki 上都没找到，但是算法本身还挺简单易懂的。

最短路生成树

这个东西实际上也没什么可说的，是什么东西看名字应该就能看懂。一般最短路生成树的题里都会说类似：删边后的图中所有节点到根节点的最短距离，与原图该点到根节点的最短距离相同。具体解法和感性证明看第一道例题就行。

例题 #1 [ABC252E] Road Reduction

题面

给定 $n$$n$ 个点 $m$$m$ 条边的无向连通简单图，每条边为 $a_i$$a_i$ 到 $b_i$$b_i$，权值为 $c_i$$c_i$。你需要构造一棵生成树，最小化点 $1$$1$ 在生成树上到其它所有点的距离和，输出生成树的所有边的序号。如果有多个方案随便输出一个即可。

Solution

模板题，最短路生成树。

以 $1$$1$ 为原点跑一遍单源最短路，也就是 Dijkstra，我们在每次松弛操作的时候记录一下是通过哪条边松弛的。最后这些边将恰好组成一棵生成树，直接输出这些边的序号即可。

大概的证明可以感性理解一下，当我们用点 $s$$s$ 的边去更新 $dis(t)$$dis(t)$ 的时候，显然此时 $s$$s$ 一定已经被更新过了，也就是已经和 $1$$1$ 连结了，所以保留当前这条边即可，这样一定会形成一个树形结构。而我们跑的是最短路，这棵生成树也一定是最优的。

Code

xxxxxxxxxx
82
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
struct Edge{
26
    Edge* nxt;
27
    int to;
28
    int val;
29
    int idx;
30
    OPNEW;
31
}ed[410000];
32
ROPNEW(ed);
33
Edge* head[210000];
34

35
int N, M;
36
ll dis[210000];
37
bool vis[210000];
38
int idx[210000];
39

40
void Dijk(void){
41
    memset(dis, 0x3f, sizeof dis);
42
    priority_queue < pair < ll, int >, vector < pair < ll, int> >, greater < pair < ll, int > > > cur;
43
    dis[1] = 0, cur.push({dis[1], 1});
44
    while(!cur.empty()){
45
        int tp = cur.top().second; cur.pop();
46
        if(vis[tp])continue;
47
        vis[tp] = true;
48
        for(auto i = head[tp]; i; i = i->nxt)
49
            if(dis[tp] + i->val < dis[SON])
50
                dis[SON] = dis[tp] + i->val, idx[SON] = i->idx, cur.push({dis[SON], SON});
51
    }
52
}
53

54
int main(){
55
    // freopen("random_01.txt", "r", stdin);
56
    // freopen("out.txt", "w", stdout);
57
    N = read(), M = read();
58
    for(int i = 1; i <= M; ++i){
59
        int s = read(), t = read(), v = read();
60
        head[s] = new Edge{head[s], t, v, i};
61
        head[t] = new Edge{head[t], s, v, i};
62
    }Dijk();
63
    for(int i = 2; i <= N; ++i)printf("%d%c", idx[i], i == N ? '\n' : ' ');
64
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
65
    return 0;
66
}
67

68
template < typename T >
69
inline T read(void){
70
    T ret(0);
71
    int flag(1);
72
    char c = getchar();
73
    while(c != '-' && !isdigit(c))c = getchar();
74
    if(c == '-')flag = -1, c = getchar();
75
    while(isdigit(c)){
76
        ret *= 10;
77
        ret += int(c - '0');
78
        c = getchar();
79
    }
80
    ret *= flag;
81
    return ret;
82
}

然后后面这几道题都和本题类似，改动不大，就不放代码了。

例题 #2 CF545E Paths and Trees

题面：求最短路生成树中边权和最小的。

题解：最短路生成树模板的基础上，在最短路松弛的时候同时判断一下等于的时候若边权更小就更新边即可。

例题 #3 AcWing 349 黑暗城堡

题面：求最短路生成树方案数。

题解：和上一题类似，松弛的时候记录一下个数，最后把个数乘起来即可。

例题 #4 CF1005F Berland and the Shortest Paths

题面：求最短路生成树并输出其中的任意 $k$$k$ 个方案。

题解：最短路生成树模板的基础上，每个节点开一个 basic_string 记录一下由哪些边松弛，然后深搜一下同时维护选择哪些边，搜到足够方案数之后直接 exit(0) 即可，水题。注意无边权，故 Dijkstra 改成 bfs 之后可以去掉一只 $\log$$\log$，但是没必要。

例题 #5 CF1076D Edge Deletion

题面：要求在图里保留至多 $k$$k$ 条边后使满足最短路生成树性质的点最多，输出方案。

题解：依然是最短路生成树，不难想到构建出最短路生成树之后，在保证和 $1$$1$ 连通的基础上保留最短路生成树上的边即可，一定最优，证明显然。具体地，从 $1$$1$ 开始深搜或宽搜最短路生成树，过程中输出 $min(k,n-1)$$\min(k, n - 1)$ 条边即可。

例题 #6 LG-P2505 [HAOI2012]道路

题面：给定 $n$$n$ 点 $m$$m$ 条边的有向图，求对于其每条边在多少条最短路径中。

题解：类似最短路生成树。首先两个性质，最短路中的一段子路径一定也是最短路，且当以某个点为原点建立最短路图（即保留所有满足最短路生成树性质的边）一定为 DAG，于是不难想到枚举每个点然后建图后跑拓朴排序。建图可以先跑一边 Dijkstra 然后枚举每条边，如果存在 $di{s}_s+val=di{s}_t$$dis_s + val = dis_t$ 那么这条边一定在最短路图中。对于枚举其中每条边在多少条路径中，可以考虑先拓朴排序处理原点到该点有多少条不同路径，记为 $cntu{p}_i$$cntup_i$，然后反向拓朴排序枚举每个点之后能连出来多少条，记为 $cntdow{n}_i$$cntdown_i$，处理完后枚举每条边，对于 $s\to t$$s \rightarrow t$ 的边，贡献即为 $cntu{p}_s\times cntdow{n}_t$$cntup_s \times cntdown_t$。

Code：

xxxxxxxxxx
129
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (ll)(1e9 + 7)
23

24
template < typename T = int >
25
inline T read(void);
26

27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    int val;
31
    int idx;
32
    bool exist;
33
    OPNEW;
34
}ed[1100000];
35
ROPNEW(ed);
36
Edge* head[2000];
37

38
int N, M;
39
int S;
40
bitset < 2000 > vis;
41
int dis[2000];
42
int from[2000];
43
ll cnt[5100];
44
int cntup[2000], cntdown[2000];
45
int ind[2000];
46

47
void Topo(void){
48
    memset(cntup, 0, sizeof cntup);
49
    memset(cntdown, 0, sizeof cntdown);
50
    queue < int > cur;
51
    basic_string < int > arr;
52
    arr += S, cur.push(S), cntup[S] = 1;
53
    while(!cur.empty()){
54
        int p = cur.front(); cur.pop();
55
        for(auto i = head[p]; i; i = i->nxt){
56
            if(!i->exist)continue;
57
            (cntup[SON] += cntup[p]) %= MOD;
58
            --ind[SON];
59
            if(!ind[SON])arr += SON, cur.push(SON);
60
        }
61
    }
62
    for(auto it = arr.rbegin(); it != arr.rend(); ++it){
63
        int p = *it;
64
        cntdown[p] = 1;
65
        for(auto i = head[p]; i; i = i->nxt)
66
            if(i->exist)
67
                (cntdown[p] += cntdown[SON]) %= MOD;
68
    }
69
}
70
void SetAns(void){
71
    for(int p = 1; p <= N; ++p)
72
        for(auto i = head[p]; i; i = i->nxt)
73
            if(i->exist)
74
                (cnt[i->idx] += (ll)cntup[p] * cntdown[SON] % MOD) %= MOD;
75
}
76

77
void Dijk(void){
78
    memset(dis, 0x3f, sizeof dis);
79
    memset(ind, 0, sizeof ind);
80
    vis.reset();
81
    priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > cur;
82
    dis[S] = 0; cur.push({dis[S], S});
83
    while(!cur.empty()){
84
        int p = cur.top().second; cur.pop();
85
        if(vis[p])continue;
86
        vis[p] = true;
87
        for(auto i = head[p]; i; i = i->nxt)
88
            if(dis[p] + i->val < dis[SON])
89
                dis[SON] = dis[p] + i->val, cur.push({dis[SON], SON});
90
    }
91
    for(int p = 1; p <= N; ++p)
92
        for(auto i = head[p]; i; i = i->nxt){
93
            i->exist = dis[p] + i->val == dis[SON];
94
            if(i->exist)++ind[SON];
95
        }
96
}
97

98
int main(){
99
    N = read(), M = read();
100
    for(int i = 1; i <= M; ++i){
101
        int s = read(), t = read(), v = read();
102
        head[s] = new Edge{head[s], t, v, i};
103
    }
104
    for(int i = 1; i <= N; ++i){
105
        S = i;
106
        Dijk();
107
        Topo();
108
        SetAns();
109
    }
110
    for(int i = 1; i <= M; ++i)printf("%lld\n", cnt[i]);
111
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
112
    return 0;
113
}
114

115
template < typename T >
116
inline T read(void){
117
    T ret(0);
118
    int flag(1);
119
    char c = getchar();
120
    while(c != '-' && !isdigit(c))c = getchar();
121
    if(c == '-')flag = -1, c = getchar();
122
    while(isdigit(c)){
123
        ret *= 10;
124
        ret += int(c - '0');
125
        c = getchar();
126
    }
127
    ret *= flag;
128
    return ret;
129
}

例题 #7 LG-P2993 [FJOI2014]最短路径树问题

最短路径树上点分治，先咕着，laterrrrr 刷点分治题的时候再做。

UPD

update-2022_12_03 初稿