水题笔记_ [SCOI2012]滑雪与时间胶囊 [图论, kruskal, 最小生成树, 翻车]

经典算法不用改一改, 就不会做了…

记得找每个变量间的联系来简化程序

懵逼的 题目

扯淡的 题解

我们发现…这个题…能到达的点一定形成了一棵树, 而且因为要”满足经过景点数最大的前提”, 所以这个图中所有从1能到达的点都要到达, 那么我们发现这就是有向图(这个图中的边是在以1为起点进行bfs的时候能经过的边)中一个固定起点的最小生成树

然而怎么求呢?

我: 直接当成无向图求

昊哥: 你sb吗, 然后丢出一张图

GG

我: …那你拓扑排序一遍, 然后先按照拓扑的编号排序分层, 然后再按照边权做最小生成树

昊哥: 你sb吗, 按照拓扑排序做出的编号不就是按照高度排序做出来的编号

我: …昊哥你收小弟嘛?

所以这个题目就是:

  • $bfs$, 找出能到达的节点, 这些节点就是你在滑雪的时候能到达的点, 记录每一条能到达的边
  • 把这些边按照终点的高度为第一关键字, 边权为第二关键字排序
  • 跑$kruskal$, $MST$的大小就是最终的花费

然后…$\downarrow:$我写的$kruskal$…然后我就重构了两遍, 调了一天… 艹

GG

沙茶的 代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**************************************************************
Problem: 2753
User: Cansult
Language: C++
Result: Accepted
Time:15072 ms
Memory:129192 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (1000000 + 5)
#define LL long long
#define int LL
using namespace std;
struct edg
{
int from, to, next, cost;
edg() {}
edg(int fr, int dqt, int nex, int dqc): from(fr), to(dqt), next(nex), cost(dqc) {}
}b[MAXM << 1], e[MAXM << 1];
int g[MAXN], cntb, n, m, na, me, he[MAXN], fa[MAXN], ans;
void adn(int from, int to, int cost)
{
b[++cntb] = edg(from, to, g[from], cost);
g[from] = cntb;
}
void bfs()
{
bool vis[MAXN];
queue<int> q;
memset(vis, false, sizeof(vis));
q.push(1), vis[1] = true;
na = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
{
e[++me] = b[i];
if (!vis[b[i].to])
vis[b[i].to] = true, ++na, q.push(b[i].to);
}
}
}
bool cmp(edg x, edg y)
{ return (he[x.to] > he[y.to] || (he[x.to] == he[y.to] && x.cost < y.cost)); }
int find(int x)
{ return (x == fa[x] ? x : (fa[x] = find(fa[x]))); }
void uni(int x, int y)
{ fa[find(x)] = find(y); }
void kruskal()
{
for (int i = 1; i <= n; i++) fa[i] = i;
sort(e + 1, e + me + 1, cmp);
int cnte = 0;
for (int i = 1; i <= me; i++)
if (find(e[i].from) != find(e[i].to))
{
uni(e[i].from, e[i].to);
ans += e[i].cost;
++cnte;
if (cnte == na - 1)
break;
}
}
main()
{
// freopen("in.in", "r", stdin);
// freopen("wa.out", "w", stdout);
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%lld", &he[i]);
for (int i = 1, srx, sry, srz; i <= m; i++)
{
scanf("%lld%lld%lld", &srx, &sry, &srz);
if (he[srx] > he[sry])
adn(srx, sry, srz);
else if (he[srx] < he[sry])
adn(sry, srx, srz);
else
adn(srx, sry, srz), adn(sry, srx, srz);
}
bfs();
kruskal();
printf("%lld %lld\n", na, ans);
return 0;
}

By 昊哥的3001号小弟 Cansult