[ABC252E] Road Reduction Solution

更好的阅读体验戳此进入

题面

给定 $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
}

UPD

update-2022_12_03 初稿