【生成树】滑雪与时间胶囊

图论

传送门：CodeVS2399

这道题目难度一般，题目原意很显然是求一个特殊限制下的最小树形图，然而数据很大，只支持O(m log m)

但是这道题的特点就是有高度，高度有什么用呢，首先是限定了方向，由于是从特定点（1号点）出发，因此只要处理出能到达哪些点（也就是求第一问），然后再用最小生成树kruskal即可

代码如下：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
LL fa[300000],FA[300000];
LL n,m,x,y,z,ans,sum,tot,t,w,now,p;
LL a[300000],q[300000],head[300000],last[300000];
bool vis[300000];
struct edge{
	LL u,v,dis,next;
	
	bool operator < (const edge x) const{
		if (a[v]==a[x.v]) return dis<x.dis;
		return a[v]>a[x.v];
	}
}
e[3000000];
void init(int n){
	for (int i=1;i<=n;i++) fa[i]=i;
}
int find(int x){
	if (x==fa[x]) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
void add(int x,int y,int z){
	tot++;
	e[tot].u=x;
	e[tot].v=y;
	e[tot].dis=z;
	if (head[x]==0)
		head[x]=tot;
	else
		e[last[x]].next=tot;
	last[x]=tot;
}
void bfs(){
	sum=1;
	q[1]=1;
	vis[1]=1;
	t=0; w=1;
	while (t<w){
		t++;
		now=q[t];
		p=head[now];
		while (p>0){
			if (!vis[e[p].v]){
				vis[e[p].v]=1;
				w++;
				sum++;
				q[w]=e[p].v;
			}
			p=e[p].next;
		}
	}
}
		
int main(){
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	
	for (int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		if (a[x]>=a[y]) add(x,y,z);
		if (a[y]>=a[x]) add(y,x,z);
	}
	
	bfs();
	
	sort(e+1,e+tot+1);
	init(n);
	for (int i=1;i<=tot;i++)
		if (vis[e[i].u] && vis[e[i].v]){
			int fu=find(e[i].u),fv=find(e[i].v);
			if (fu!=fv){
				fa[fv]=fu;
				ans+=e[i].dis;
			}
		}
		
	printf("%lld %lld\n",sum,ans);
	
	return 0;
}