5月1日 [SCOI2012]滑雪与时间胶囊 最小生成树

思路：因为只能从高度高到高度低。那么边就是有向的。而且最后一定是一棵树。
第一问，直接dfs就可以了。标记可以到达的点。第二步，把这些点之间的边提出来。然后跑一个kruskal就可以了。边的排序：如果高度不一样，高度高的在前面，如果高度一样，边短的在前面。因为我们总是先访问高度高的边。如果直接按高度小的在前。这个样例：

3 3
3 2 1
1 3 2
1 2 8
2 3 4
就过不了
#include<bits/stdc++.h>
#define LL long long
using namespace std;

vector<vector<int> > v(1000005);
int h[1000005], vis[1000005], f[1000005], cut=0;
struct E{
    int u, v, k;
}e[2000005];

void DFS(int u){
    vis[u]=1;
    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(!vis[to]&&h[u]>=h[to]){
            DFS(to); cut++;
        }
    }
}

int fd(int x){
    return (f[x]==x)?x:f[x]=fd(f[x]);
}

int main(){
    int n, m; scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%d", &h[i]); f[i]=i;
    }
    int x, y, k;
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &x, &y, &k);
        v[x].push_back(y);
        v[y].push_back(x);
        e[i]={x, y, k};
    }
    DFS(1);
    int tot=0;
    for(int i=1; i<=m; i++){
        x=e[i].u, y=e[i].v;
        if(vis[x]&&vis[y]){
            if(h[x]>=h[y]){
                e[++tot]=e[i];
            }
            else{
                e[++tot]=e[i];
                swap(e[tot].u, e[tot].v);
            }
        }
    }
    sort(e+1, e+1+tot, [](E &a, E &b){ return a.k<b.k;});
    LL ans=0;
    for(int i=1; i<=tot; i++){
        x=fd(e[i].u), y=fd(e[i].v);
        if(x!=y){
            f[x]=y; ans+=e[i].k;
        }
    }
    printf("%d %lld\n", cut+1, ans);

    return 0;
}