题意

• 给定n个点，每个点有自己的高度，给定m条边，边总是由高的点指向低的点
• 特别的，两个点一样高，就认为是双向边
• 求出最多能到达的点的个数，以及到达这些点需要的最小距离

思路

• 先dfs一遍，确定哪些点能到
• 类似于最小生成树，但是最小生成树需要保证边都是无向边，因为最小生成树加入一条边本质上是两个点之间能联通
• 到这个题，由任意点都只能向下访问各个点，所以，Prim的排序就不再只按照长度排序，而是先按照高度(保证尽可能访问更多点)，再按照长度
• 而如果使用Kruskal，给边排序的时候也是按照边中较低的点进行排序，使得终点最高，然后再按长度排序，拿到一条边的时候从高的地方走向矮的地方，那就要保证，高的那个点是可以走到的，不然就会出问题

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

struct ty{
    int x,y,l,h;
}edge[1010110];
vector<int> bian[1010110];
int h[1010110],fa[1010110];
int vis[101010];
long long num,ans;
int n,m;

bool cmp(ty a,ty b){
    if(a.h==b.h) return a.l<b.l;
    else return a.h>b.h;
}

void dfs(int x){
    num++;
    vis[x]=1;
    for(auto i:bian[x]){
        if(vis[i])continue;
        dfs(i);
    }
}

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> h[i];
    for(int i=1;i<=m;i++){
        int a,b,k;
        cin >> a >> b >> k;
        if(h[a]>=h[b]) bian[a].push_back(b);
        if(h[b]>=h[a]) bian[b].push_back(a);
        edge[i].x=a;
        edge[i].y=b;
        edge[i].l=k;
        edge[i].h=min(h[a],h[b]);
    }
    dfs(1);
    sort(edge+1,edge+m+1,cmp);
    // for(int i=1;i<=m;i++) cout << edge[i].x << ' ' << edge[i].y << endl;
    // for(int i=1;i<=n;i++) cout << vis[i] << ' ';
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int tx=edge[i].x;
        int ty=edge[i].y;
        int fx=find(tx);
        int fy=find(ty);
        if(!vis[ty]||!vis[tx]||fx==fy) continue;
        ans+=edge[i].l;
        fa[fx]=fy;
    }
    cout << num << ' ' << ans << endl;
}