[SCOI2012]滑雪

问：景点数最大的同时 滑行总距离最小

景点数最大 即求 最大连通块

滑行总距离最小 即求 最小生成树

对于多条件问题 有限考虑硬性条件（可行性） 再考虑最优性

1.可行性

滑行必须从高到低（相等也可），即更新节点时必然是从高的点更新低的点，

所以选择节点时 优 先 考虑高的节点

结论 对所有节点从高到低排序

2.最优性

与最小生成树同理

优先选择长度最短的边

结论 对所有边从小到大排序

3.坑点

1. 当两个点高度相等是，是双向边
2. 既然是双向边，就要开两倍数组，否则RE
3. 只考虑了最优性而没有考虑可行性

4.代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const ll N = 1e5+7, M = 2 * 1e6+7, INF = 5e9+9; // 可能存在双向边
ll n,m,h[N];
ll head[N],tot;
struct edge
{
	ll ver,dis,nex;
}e[M],pe[M];
void add(ll u,ll v,ll w)
{
	e[++tot].nex = head[u];
	e[tot].ver = v;
	e[tot].dis = w;
	head[u] = tot;
}
ll phead[N],ptot;
void padd(ll u,ll v,ll w)
{
	pe[++ptot].nex = phead[u];
	pe[ptot].ver = v;
	pe[ptot].dis = w;
	phead[u] = ptot;
}
bool arr[N];
ll num;
void bfs(ll begin)
{
	queue<ll> q;
	arr[begin] = 1;
	num++;
	q.push(begin);
	
	while(q.size())
	{
		ll now = q.front();
		q.pop();
		for(ll i=head[now];i;i=e[i].nex)
		{
			padd(now,e[i].ver,e[i].dis);
			if(arr[e[i].ver])continue;
			arr[e[i].ver] = 1;
			num++;
			q.push(e[i].ver);
		}
	}
}
struct cmp
{
	bool operator()(edge a,edge b)
	{
		if(h[a.ver]!=h[b.ver])return h[a.ver] < h[b.ver];//可行性
		return a.dis>b.dis;//最优性
	}
};
ll dis[N],sum;
void prim(ll begin)
{
	priority_queue< edge , vector<edge> , cmp > q;
	for(ll i=1;i<=n;i++)dis[i]=INF;
	dis[begin] = 0;
	for(ll i=phead[begin];i;i=pe[i].nex)
	{
		if(dis[begin] + pe[i].dis < dis[pe[i].ver])
		{
			q.push(pe[i]);
			dis[pe[i].ver]=pe[i].dis;
		}
	}
	while(q.size())
	{
		edge now = q.top();
		q.pop();
		if(!dis[now.ver])continue;
		dis[now.ver]=0;
		sum+=now.dis;
		for(ll i=phead[now.ver];i;i=pe[i].nex)
		{
			if(dis[begin] + pe[i].dis < dis[pe[i].ver])
			{
				dis[pe[i].ver] = pe[i].dis;
				q.push(pe[i]);
			}
		}
	}
}
int main()
{
	n = read();
	m = read();
	for(ll i=1;i<=n;i++)h[i]=read();
	for(ll i=1;i<=m;i++)
	{
		ll u,v,w;
		u=read();
		v=read();
		w=read();
		if(h[u]<=h[v])add(v,u,w);
		if(h[u]>=h[v])add(u,v,w);
	}
	bfs(1);//事实上不需要BFS
	prim(1);
	printf("%lld %lld",num,sum);
	return 0;
}