滑雪与时间胶囊题解

题解：其实看到这句话a180285喜欢用最短的滑行路径去访问尽量多的景点，就很明显是一个最小生成树了，但是有点区别的是每个点只可以由高到低，而且每个点是从开始，那么我们就可以先处理每个表，首先以他们的高度从高到底排序，然后在以他们的边权由低到高排序，是不是一个克鲁斯就出来啦，套上你的板子就直接搞。Prim还没有时间来搞 准备明天看看

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const int maxx=1e6+7;
const int mod=1e9+7;
int fa[maxx],vis[maxx];
int hall[maxx];
int n,m;
struct node{
  int u,v,w,next;
    bool operator < (const node&a)const{
     if(hall[v]==hall[a.v]) return w<a.w;///边长权值升序
       return hall[v]>hall[a.v];
    }

};
node ans[maxx<<1];
int head[maxx],cnt=0;
ll sum=0,tot=1;
void add(int u,int v,int w)
{
    cnt++;
    ans[cnt].u=u;
    ans[cnt].v=v;
    ans[cnt].w=w;
    ans[cnt].next=head[u];
    head[u]=cnt;
}
void bfs(int x)
{
    vis[x]=1;
    queue<int>s; s.push(x);
    while(!s.empty())
    {
        int u=s.front();s.pop();
        for(int i=head[u];i;i=ans[i].next)
        {
            int v=ans[i].v;
            if(!vis[v])
            {
                s.push(v);
                tot++;
                vis[v]=1;
            }
        }
    }
}
int fd(int x)
{
    if(fa[x]!=x)
    {
        fa[x]=fd(fa[x]);
    }
    return fa[x];
}
void kruskal()
{
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=cnt;i++)
    {
        int u=ans[i].u,v=ans[i].v,w=ans[i].w;
        if(vis[u]&&vis[v])
        {
            if(fd(u)!=fd(v))
            {
                fa[fd(u)]=fd(v);
                sum+=w;
            }
        }
    }
}
int main()
{
    fio;
   // scanf("%d%d",&n,&m);
     n = read(), m = read();
    for(int i=1;i<=n;i++)
      hall[i] = read();   //scanf("%d",&hall[i]);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        u = read(), v = read(), w = read();  //scanf("%d%d%d",&u,&v,&w);
        if(hall[u]>=hall[v]) add(u,v,w);
        if(hall[u]<=hall[v])  add(v,u,w);
    }
    bfs(1);
    sort(ans+1,ans+1+cnt);
    kruskal();
    printf("%lld %lld",tot,sum);
    return 0;
}