最小生成树MST

基础方法有\(Kruskal\),\(Prim\)和\(B\)算法，就不多说了。

P2573

注意到这是个有向图，所以不能直接的跑\(kruskal\).

第一问就直接\(dfs\)求出点数，注意我们只要\(h[u]\geq h[v]\)的边。并且，要将每个点拓展到的边记录下来，作为第二问的新图。

第二问中，我们要将边按终点高度为第一关键字从大到小排序，边权为第二关键字从小到大排序。

至于为什么只有这样才对，考虑这组数据~~made by AKonjac_~~

4 4
4 3 2 1
1 3 1000000001
1 2 1000000004
2 3 1000000002
2 4 1000000003

如果只按边权从小到大排序，生成的最小生成树无法到达\(2\)号点，所以错误。换句话说，为了保证有向生成树一定联通，就要按照终点从大到小的顺序更新。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long 
using namespace std;
const int N=1e5+10,M=1e6+10;
struct edge{
    int u,v,w,nxt;
}e[M<<1],E[M<<1];
int fa[N],vis[N],head[N],Head[N],h[N];
int cnt,Cnt,tot,nod,u,v,w,n,m;
ll ans;
int getfa(int u){
    return fa[u]==u?u:fa[u]=getfa(fa[u]);
}
void add(int u,int v,int w){
    e[++cnt].u=u,e[cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}
void Add(int u,int v,int w){
    E[++Cnt].u=u,E[Cnt].v=v,E[Cnt].w=w,E[Cnt].nxt=Head[u],Head[u]=Cnt;
}
void dfs(int u){
    vis[u]=1;++tot;
    for(int i=head[u];~i;i=e[i].nxt){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        Add(u,v,w);
        if(!vis[v]) dfs(v);
    }
} 
bool Cmp(edge a,edge b){
    if(h[a.v]==h[b.v]) return a.w<b.w;
    return h[a.v]>h[b.v];
}
int main(){
    memset(head,-1,sizeof head);cnt=-1;
    memset(Head,-1,sizeof Head);Cnt=-1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&h[i]);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        if(h[u]>=h[v]) add(u,v,w);
        if(h[u]<=h[v]) add(v,u,w);
    }
    dfs(1);
    sort(E,E+Cnt+1,Cmp);nod=0;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=0;i<=Cnt;++i){
        int u=E[i].u,v=E[i].v; ll w=(ll)E[i].w;
        int uu=getfa(u),vv=getfa(v);
        if(uu!=vv){
            fa[uu]=vv;
            ans+=w;++nod;
        }
        if(nod>=tot-1) break;
    }
    printf("%d %lld",tot,ans);
    return 0;
}