题解

思路分析

这是一道 最小生成树 + BFS + 贪心 的综合问题。

问题建模

• 从起点1开始，在高度限制下访问尽可能多的景点
• 可以使用时间胶囊回溯（类似于树上遍历）
• 目标：访问景点数最多，且总滑行距离最小

核心思路

1. 高度限制

只能从高度 $\geq$ 的点滑向高度 $\leq$ 的点，所以：

• 只考虑高度 $\leq h_1$ 的景点
• 对于边 $(u, v)$，只有当 $h_u \geq h_v$ 时才能从 $u$ 滑向 $v$

2. BFS 找可达点

从起点1开始 BFS，找到所有可达的景点（高度限制下）。

3. 最小生成树

在可达点中，使用 Kruskal 算法求最小生成树：

• 按边权排序
• 优先按目标点高度降序（确保能滑行）
• 使用并查集合并

关键：最小生成树保证了访问所有可达点的最小代价。

算法步骤

1. 预处理：

   • 读入数据，建图
   • 只保留满足高度条件的边

2. BFS 找可达点：

   • 从起点1出发
   • 标记所有可达点

3. Kruskal 求MST：

   • 将边按高度和权重排序
   • 使用并查集合并
   • 累加边权

4. 输出结果：

   • 统计连通分量中的点数
   • 输出总边权

复杂度分析

• BFS：$O(N + M)$
• 排序：$O(M \log M)$
• Kruskal：$O(M \alpha(N))$
• 总时间复杂度：$O(M \log M)$
• 空间复杂度：$O(N + M)$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10,M=1e6+10;
int n,m,h[N],cnt=0,fa[N];
int vis[N],sum=0;
ll ans=0;
vector<int> g[N];
struct edge{int u,v,w;}e[M<<1];

void bfs(){
	queue<int> q;
	vis[1]=1,q.push(1);
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(int v:g[x])
			if(!vis[v]&&h[v]<=h[x]) vis[v]=1,q.push(v);
	}
}

bool cmp(edge a,edge b){
	if(h[a.v]==h[b.v]) return a.w<b.w;
	return h[a.v]>h[b.v];
}

int find(int x){
	return fa[x]=(x==fa[x])?x:find(fa[x]);
}

void merge(int x,int y){
	int i=find(x),j=find(y);
	fa[i]=j;
}

void Kruskal(){
	for(int i=1;i<=cnt;i++){
		if(!vis[e[i].u]||!vis[e[i].v]) continue;
		if(find(e[i].u)==find(e[i].v)) continue;
		merge(e[i].u,e[i].v),ans+=e[i].w;
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int u,v,w; cin>>u>>v>>w;
		if(h[u]<h[v]) swap(u,v);
		if(h[u]<=h[1]){
			e[++cnt]={u,v,w};
			if(h[u]==h[v]) e[++cnt]={v,u,w};
			g[u].push_back(v),g[v].push_back(u);
		}
	}
	sort(e+1,e+cnt+1,cmp);
	bfs();
	Kruskal();
	int f=find(1);
	for(int i=1;i<=n;i++) if(find(i)==f) sum++;
	cout<<sum<<" "<<ans<<endl;
	return 0;
}

题解

滑雪只能沿着高度不升的轨道前进，因此我们先从 1 号景点出发做一次 BFS，仅保留满足 H[u] ≥ H[v] 的有向边，把所有能够到达的景点标记出来；这些点的数量就是可以游览的最大景点数。随后只在这个可达子图上考虑轨道，针对每条原始无向边按照高度关系至多保留一个方向（高→低），并按“终点高度从高到低、同高度下长度从小到大”的顺序排序。这样用 Kruskal 在这些有向边上生成一棵（或若干棵）最小生成树，就能保证在覆盖全部可达景点的前提下，滑行总距离最小。由于时间胶囊可以让滑雪者在树上随意回溯，树结构即可满足行程需要，输出的就是最多可达景点数以及对应的最短滑行距离和。

// 只能从点权大的点到小的点，于是这么建边
// 那么显然我们需要的是一个树形结构，这样每条边最多走一次
// 那么搜索出所有能到达的点再Kruscal？
// 在落点高度相同的情况下，我们优先选择边权最小的
// 否则我们必须考虑更高的，以保证正确性
//#define DEBUG

#ifdef DEBUG
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<time.h>
#include<string.h>
#include<memory.h>
#include<random>
#include<unordered_map>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<deque>
#include<algorithm>
#endif

#ifndef DEBUG
#include<bits/stdc++.h>
#endif

using namespace std;

bool MEMST;
int clock_st = clock();
#define ll long long
#define ull unsigned long long
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second
#define il inline
#define reg register
#define ld long double
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define LEFT (POS*2)
#define RIGHT (POS*2+1)
#define lc(x) tr[x].l ? tr[x].l : tr[x].l=++tlt
#define rc(x) tr[x].r ? tr[x].r : tr[x].r=++tlt
#define lll __int128
mt19937_64 engine(time(0));
const ll N = 1e5+5;
const ll M = 2e6+5;
vector<pii> E[N];
ll n,m,H[N],tlt,fa[N];
struct Edge{
	ll u,v,w;
	il bool operator <(const Edge &ano){
		if(H[v] == H[ano.v]) return w < ano.w;
		return H[v] > H[ano.v];
	}
} Edges[M], G[M];

bool bfsvis[N];

il void bfs(){
	queue<ll> Q; bfsvis[1]=1; Q.push(1);
	while(!Q.empty()){
		ll u=Q.front(); Q.pop();
		for(pii ed : E[u]){
			ll v=ed.fi, w=ed.se;
			if(bfsvis[v]) continue;
			bfsvis[v]=1;
			Q.push(v);
		}
	}
	return ;
}

il ll find(ll x){
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}

il void unity(ll tx, ll ty){
	ll fa1=find(tx), fa2=find(ty);
	if(fa1==fa2) return ;
	fa[fa1] = fa2;
	return ;
}

il pii Kruscal(){
	ll ans1=0,ans2=0;
	sort(G+1, G+tlt+1);
	for(ll i=1; i<=n; i++){
		fa[i]=i;
		if(bfsvis[i]) ans1++;
	} 
	for(ll i=1; i<=tlt; i++){
		ll u=G[i].u, v=G[i].v, w=G[i].w;
		if(find(u)==find(v)) continue;
		unity(u, v);
		ans2 += w;
	}
	return {ans1, ans2};
}

bool MEMED;
signed main() {
	fastio;
	cin >> n >> m;
	for(ll i=1; i<=n; i++) cin >> H[i];
	for(ll i=1; i<=m; i++){
		ll u,v,k;
		cin >> u >> v >> k;
		Edges[i] = {u,v,k};
		if(H[u]>=H[v]) E[u].pb({v,k});
		if(H[v]>=H[u]) E[v].pb({u,k});
	}
	bfs();
	for(ll i=1; i<=m; i++){
		if(bfsvis[Edges[i].u] && bfsvis[Edges[i].v]){
			ll u=Edges[i].u, v=Edges[i].v, w=Edges[i].w;
			if(H[u]>=H[v]) G[++tlt] = {u,v,w};
			if(H[u]<=H[v]) G[++tlt] = {v,u,w};
		}
	}
	pii ans = Kruscal();
	printf("%lld %lld\n", ans.fi, ans.se);
	
	#ifdef DEBUG
	printf("time: %lld ms\n", (ll)(((double)clock() - clock_st) * 1000.0 / CLOCKS_PER_SEC));
	printf("memory: %.2lf MB\n", (double)abs((&MEMED - &MEMST) / 1024.0 / 1024.0));
	#endif
	return 0;
}