NC20568 [SCOI2012]滑雪与时间胶囊

题目地址：

https://ac.nowcoder.com/acm/problem/20568

基本思路：

先吐槽一下这题题面里是不是没给数据范围啊QwQ
这题我们首先会发现这个高度很重要，因为有高度的限制那么这个这个无向图实际上就能构造成一个有向图。
那么我们先想他一共能走几个景点，这个很简单一遍dfs统计就完事了。
问题是他还要求最短滑行距离，因为时光胶囊的原因我们可以发现实际上这是一棵生成树，但是由于高度限制这又是一个有向图，所以我们会考虑最小树形图(然而我不会最小树形图)，但是这题却不是使用最小树形图来解决，而且关键在还是在这个高度上面。
我们考虑如果使用kuskal算法求有向图最小生成树不对在什么地方，由于kuskal算法不考虑边的方向那么就会出现集合外一点能到达集合内，但集合内的点并不能到达这个集合外的点，结果这条边还加入了集合的情况。那么kuskal算法就是要加入集合内往集合外连的那些边，集合内往集合外，高度高往高度低这样一看就很明显了，把边按终点高度从大到小排序，相同高度再按照边权从小到大排序，就能保证加入的边一定是集合内往集合外的边的同时还是最小的。所以我们只要统计和在dfs中走的到的那些点相连的边，再按照上面的排序规则跑kuskal算法，就能得到答案了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 2020000;
int n,m,h[maxn];
int ans1 = 0,ans2 = 0;
struct Edge{
  int to,next;
}edge[maxn];
struct eg{
  int u,v,w;
  //这样排序之后,集合内往集合外的边就一定会先加进来;
  bool operator < (const eg &e) const {
    if(h[v] == h[e.v]) return w < e.w;
    return h[v] > h[e.v];
  }  
}memo[maxn];
int cnt = 0,head[maxn];
void add_edge(int u,int v){edge[++cnt] = {v,head[u]}; head[u] = cnt ;}
//dfs部分;
bool vis[maxn];
void dfs(int u){
  vis[u] = true; ++ans1;
  for(int i = head[u] ; i!=-1 ; i = edge[i].next){
    if(!vis[edge[i].to]) dfs(edge[i].to);
  }
}
//并查集部分;
int par[maxn];
void init(){rep(i,0,n) par[i] = i;}
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]);}
bool same(int x,int y) { return find(x) == find(y); }
void unite(int x,int y){
  x = find(x),y = find(y);
  if(x == y) return;
  par[x] = y;
}
signed main() {
  IO;
  cin >> n >> m;
  rep(i,1,n) cin >> h[i];
  cnt = 0;mset(head,-1);
  rep(i,1,m){
    int u,v,w;
    cin >> u >> v >> w;
    if(h[u] >= h[v]) add_edge(u,v);
    if(h[v] >= h[u]) add_edge(v,u);
    memo[i] = {u,v,w};
  }
  mset(vis,false);
  dfs(1);
  vector<eg> vec;
  rep(i,1,m){
    //运行kuskal算法的边一定要是从1出发能到达的那些点之间的边;
    if(vis[memo[i].u] && vis[memo[i].v]){
      int u = memo[i].u,v = memo[i].v,w = memo[i].w;
      if(h[u] >= h[v]) vec.push_back({u,v,w});
      if(h[v] >= h[u]) vec.push_back({v,u,w});
    }
  }
  init();
  int sz = 0;
  sort(vec.begin(),vec.end());
  for(auto it : vec){
    if(!same(it.u,it.v)){
      unite(it.u,it.v);
      sz++;
      ans2 += it.w;
    }
    if(sz == ans1 + 1) break;//联通了就break;
  }
  cout << ans1 << " " << ans2 << '\n';
  return 0;
}