【最小生成树】BZOJ2753 [SCOI2012]滑雪与时间胶囊

题面在这里

​

第一问就是能遍历到的点数

考虑第二问，肯定是尽量先走较高的点，高度相同时再走边权小的

这样才能在遍历最多点的情况下走最短的路

那么高度第一关键字，边权第二关键字排序，做最小生成树即可

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn=100005,maxe=2000005;
int n,m,e,h[maxn],nn;
struct edge{
	int x,y,w;
	bool operator<(const edge&b)const {return h[y]>h[b.y]||h[y]==h[b.y]&&w<b.w;}
}a[maxe];
int tot,son[maxe],nxt[maxe],lnk[maxn];
inline void add(int x,int y){
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
int que[maxn];
bool vis[maxn];
void bfs(){
	int hed=0,til=1;
	que[1]=1;vis[1]=1;
	while (hed!=til){
		int x=que[++hed];
		for (int j=lnk[x];j;j=nxt[j])
		 if (!vis[son[j]]) vis[que[++til]=son[j]]=1;
	}
	nn=til;
}
int fa[maxn];
inline int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main(){
	scanf("%d%d",&n,&e);
	for (int i=1;i<=n;i++) scanf("%d",&h[i]);
	for (int i=1;i<=e;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
		if (h[a[i].x]<h[a[i].y]) swap(a[i].x,a[i].y);
		add(a[i].x,a[i].y);
		if (h[a[i].x]==h[a[i].y]) add(a[i].y,a[i].x);
	}
	bfs();
	sort(a+1,a+1+e);
	for (int i=1;i<=n;i++) fa[i]=i;
	ll ans=0;
	for (int i=1;i<=e;i++)
	 if (vis[a[i].x]&&vis[a[i].y])
	 if (getfa(a[i].x)!=getfa(a[i].y)){
	 	fa[getfa(a[i].x)]=getfa(a[i].y);
	 	ans+=a[i].w;
	 }
	printf("%d %lld",nn,ans);
	return 0;
}