[SCOI2012]滑雪与时间胶囊

题意:给定 个点高度,和 条边,以及 条边的权值然后问,从1号点能到多少个点,并且所有能到的点的权值求和最小是多少
题解:第一问:明显的广搜直接解决,记得标记下点
第二问:因为可以返回到上面的任意的点,所以我们每去一个点,可以直接到与他相连且最近的那个点过去,(越解释越乱......)
其实就是最小生成树

比如我们从1点的一条边出去,把能连的点全部连上之后,相当于是一个集合,然后再加入1点可以到的,还没有加入集合的点,因为可以回溯到原来的某一个时间点,所以直接找距离集合最近的点,先加入,...然后重复
时间复杂度:搜索是: ,最小生成树是:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define MAXN 100001
#define MAXE 2000001
struct EDGE{int from,to,value,height,next;};
EDGE a[MAXE];
int N,M,tot=0,last[MAXN];
bool vis[MAXN];
int Q[MAXE],ans1,fa[MAXN],H[MAXN];
long long ans2=0LL;
bool cmp(EDGE X,EDGE Y)
{
      if(X.height==Y.height)   return X.value<Y.value;
      return X.height>Y.height;
}
int get(int x){return fa[x]==x ? x : fa[x]=get(fa[x]);}
void add(int from,int to,int value)
{
      a[++tot].from=from;
      a[tot].to=to;
      a[tot].value=value;
      a[tot].height=H[to];
      a[tot].next=last[from];
      last[from]=tot;
}
void bfs()
{
      int right=1;
      Q[1]=1;ans1=1;
      vis[1]=true;
      for(int i=1;i<=right;i++)
      {
            int now=Q[i];
            for(int j=last[now];j;j=a[j].next)
            {
                  if(!vis[a[j].to])
                  {
                        vis[a[j].to]=true;
                        ans1++;
                        Q[++right]=a[j].to;
                  }
            }
      }
}
void kruskal()
{
      int tot1=0;
      sort(a+1,a+1+tot,cmp);
      for(int i=1;i<=N;i++)  fa[i]=i;
      for(int i=1;i<=tot;i++)
      {
            if(!(vis[a[i].from] && vis[a[i].to]))   continue;
            int fx=get(fa[a[i].from]);
            int fy=get(fa[a[i].to]);
            if(fx!=fy)
            {
                  fa[fy]=fx;
                  tot1++;
                  ans2+=(long long)a[i].value;
            }
            if(tot1==ans1-1)   break;
      }
}
int main()
{
      scanf("%d%d",&N,&M);
      for(int i=1;i<=N;i++)
            scanf("%d",&H[i]);
      for(int i=1;i<=M;i++)
      {
            int A,B,C;
            scanf("%d%d%d",&A,&B,&C);
            if(H[A]>=H[B])   add(A,B,C);
            if(H[A]<=H[B])   add(B,A,C);
      }
      bfs();
      kruskal();
      printf("%d %lld\n",ans1,ans2);
      return 0;
}