每日一题 5月1日 滑雪与时间胶囊 有向图的最小生成树+贪心

prim和Kruskal太久不打，都忘光啦。

题目大意：
给n个点和m条边，每个点有一个高度h[i]，给定的m条边都有三个参数u,v,k表示u和v点有一天长度为k的边。其中这条边只能从高度高的地方连向高度低的地方。（两个点高度相同时就是无向边，否则是有向边）
现在你可以从点1开始，问最多可以访问到的点的数量，以及在访问尽量多的点的前提下，让总路程最短。
他有一种特异功能，可以无消耗无限制的回到之前去过的点。
n<=10^5,m<=10^6

思路：
首先根据题意我们可以完成建图。然后判断最多的点数量，我们可以从1开始直接bfs或者dfs求连通块数量。
接着考虑第二个问题，其实如果是无向图，就变成最小生成树了。但是本题是有向图，有向图不能直接套最小生成树，因为可能本身选的这条边是非连通块内的或者是不能直接到达的，据说求有向图的最小生成树叫做最小树形图，据说解决的算法叫做朱刘算法，复杂度是O(n^3)。本题显然不可能。
参考了题解，解法比较巧妙。
对边按照指向点的高度排序，高度相同按长度排序。
然后进行Kruskal求解。
这样做可以解决问题的原因在于，我们先取的边一定是高度更高的边，把高度较高的取完以后，再去看高度低的边，就可以保证不会出现先取了高度低的边。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,h[100040],tot,head[100040],vis[100040];
int fa[100040];
long long sum;
int finda(int x){
    if(x!=fa[x])fa[x]=finda(fa[x]);
    return fa[x];
}
struct node{
    int u,to,next,w;
    bool operator <(const node& a)const{
        if(h[to]==h[a.to])return w<a.w;
        return h[to]>h[a.to];
    } 

}e[2000400];
void init(){
    tot=0;
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
}
void add(int a,int b,int c){
    tot++;
    e[tot].u=a;
    e[tot].to=b;
    e[tot].next=head[a];
    e[tot].w=c;
    head[a]=tot;
}
int ans;
void dfs(int x){
    vis[x]=1;
    ans++;
    for(int i=head[x];~i;i=e[i].next){
        int y=e[i].to;
        if(vis[y])continue;
        dfs(y);
    }
}
void kruskal(int x){
    for(int i=0;i<=n;i++)fa[i]=i;
    int cnt=1;
    for(int i=1;i<=tot;i++){
        int u,v;
        u=e[i].u;v=e[i].to;

        if(vis[u]&&vis[v]){
            u=finda(u);v=finda(v);
            if(u!=v){
                 fa[u]=v;
                sum+=e[i].w;
            }

        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>h[i];
    init();
    for(int i=1;i<=m;i++){
        int u,v,k;
        scanf("%d%d%d",&u,&v,&k);
        if(h[u]>h[v])add(u,v,k);
        else if(h[u]<h[v])add(v,u,k);
        else {
            add(u,v,k);add(v,u,k);
        }
    }
    dfs(1);
    sort(e+1,e+1+tot);
    kruskal(1);
    cout<<ans<<' '<<sum<<endl;
}