题目
https://www.luogu.com.cn/problem/P2573
由于变量名实在抽象，可能再过几天我自己都看不懂这个变量是什么意思了，所以我更改的更正规了一点
题目大意就是说：有好几座山，你站了一号，你只能滑倒比你低的山去看风景，然后你有药水，可以回到你前一个到的地方，或者前前一个，或者前.....前一个，简单说就是可以无限的喝这个药水
题目读完就可以很明显的发现是最小生成树了，关于最小生成树，最直观的理解就是,给一个村庄里拉一条电线，要求电可以输送到每一户人家，然后要求这个线最短
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1000005;
int n,m,h[MAXN],fa[MAXN];
bool vis[MAXN];
struct Edge{int u,v,w;
};
vector<Edge>all_edges;
vector<pair<int,int>>adj[MAXN];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int bfs(){int cnt=0;queue<int>q;q.push(1);vis[1]=true;while(!q.empty()){int u=q.front();q.pop();cnt++;for(auto&edge:adj[u]){if(!vis[edge.first]){vis[edge.first]=true;q.push(edge.first);}}}return cnt;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>h[i];fa[i]=i;}for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;if(h[u]>=h[v]){adj[u].push_back({v,w});all_edges.push_back({u,v,w});}if(h[v]>=h[u]){adj[v].push_back({u,w});all_edges.push_back({v,u,w});}}int maxx=bfs();sort(all_edges.begin(),all_edges.end(),[](const Edge&a,const Edge&b){if(h[a.v]!=h[b.v])return h[a.v]>h[b.v];return a.w<b.w;});int minn=0;for(auto&e:all_edges){if(!vis[e.u])continue;int rootU=find(e.u),rootV=find(e.v);if(rootU!=rootV){fa[rootV]=rootU;minn+=e.w;}}cout<<maxx<<" "<<minn<<endl;return 0;
}
代码详解：
bfs部分
int bfs(){int cnt=0;queue<int>q;q.push(1);vis[1]=true;while(!q.empty()){int u=q.front();q.pop();cnt++;for(auto&edge:adj[u]){if(!vis[edge.first]){vis[edge.first]=true;q.push(edge.first);}}}return cnt;
}
这个就是最经典的bfs了，唯一要注意的就是bfs过程中的那个vis数组的记录，这个是对后面有帮助的，因为，你把高度差合法的边都读到all_edges进去了，但是，有些边你可能根本就到不了
我举个例子：
你站在1号点也就是题目要求的起点，是100 迷
2-3是300->200 也就是说2->3这个路线是可行的，这个是会被读到all_edges里面去的，但是，你的起点是1，你根本就到不了2号处，也就说你后面用kruskal来求最小生成树的时候，这个边就不应该出现在all_edges里面
但是你把它读进来了，这就会导致结果是偏大的，所以这vis数组就起作用了
建立边
for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;if(h[u]>=h[v]){adj[u].push_back({v,w});all_edges.push_back({u,v,w});}if(h[v]>=h[u]){adj[v].push_back({u,w});all_edges.push_back({v,u,w});}}
排序
排序环节在kruskal算法中是必要的，但是这里先按照高度排序，再按照经典的边的权值排序，为什么要按照高度先排个序呢？这个是这道题的重点（我是这么认为的）
首先，kruskal是不可以用于有向图的，它只能用于无向图，其实最小生成树这个概念就是给无向图的，有向图的那个叫最小树形图
我举个例子
2->1 边长是1
3->2 边长是2
1->2 1000
1>3 1000
如果是用kruskal的话，经过排序之后会选第一条边和第二条边，然后123都在并查集中了，在kruskal眼中，任务已经完成了，但是有向图中，就这两条边根本不可以足以建立起123之间的联通，因为甚至从1出发哪里都去不了，因为这是个有向图
同理，对于prim，我也举个例子
1->2 10
3->2 1
1->3 100
如果用prim，结果是110 （先选1->2,再选1->3）但是真正的这个有向图的结果应该是101那么，这个题也是个有向图啊，为什么这里就可以用？
就是因为这个按照高度排序，我们按照高度排序后，想要知道这个经过这些景点最少的路线，其实就是一个简单的贪心，因为路线肯定是从高到低，用kruskal的方法，当这些点被包裹进一个并查集的时候，就肯定可以满足
不会出现上面的例子就是并查集把点包括进去结果不满足条件的情况
sort(all_edges.begin(),all_edges.end(),[](const Edge&a,const Edge&b){if(h[a.v]!=h[b.v])return h[a.v]>h[b.v];return a.w<b.w;});
经典kruskal
int minn=0;for(auto&e:all_edges){if(!vis[e.u])continue;//这个vis就是在这里发挥作用的，如果这条边不可达，那就不用kruskal，答案就不会偏大int rootU=find(e.u),rootV=find(e.v);if(rootU!=rootV){fa[rootV]=rootU;minn+=e.w;}}