https://www.luogu.com.cn/problem/P2573
题意：给定一个 n个点m条有权边图，只能从点权高的点走到低的，起点是1号点，且可以不计路程的返回至之前走过的某个点，求经过最多点的最短路径。
n<1e5,m<1e6,点权边权<1e9
思路：
1.建图：对于两点之间的边，先判断点的权值再进行指向，如果点权值一样，需要存双向边
2.求可达点的数量，对原图用dfs/bfs求出可达点的数量并标记
2.将标记的点作为一张新图，考虑最短路径，求最小生成树
3.用Kruskal算法求最小生成树，需要对边进行排序，第一关键字是边终点的高度，第二关键字是路径长度。在遍历所有边的时候，可以通过判断边的起点和终点是否标记来滤去无用的边，防止数据越界，边的数组大小需要开到2m。（将边起点高度作为第一关键字不能保证顺序，样例都过不了）
4.防止溢出，最小生成树结果用longlong保存。
5.用dfs/bfs遍历图的存边方式和Kruskal不同，需要存2次边。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<vector> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f///负无穷小 -0x7f using namespace std; const int maxx=1e6+5; int n,m; int h[maxx]; int par[maxx]; int vis[maxx]; int num,cnt;///有效边数 ，可达点数， ll sum;///总最短距离 struct Edge///Kruskal存边 { int u,v,w; }; Edge e[maxx*2]; struct Edge2///dfs存边 { int v,w; }; vector<Edge2>a[maxx]; void init() { for(int i=1;i<=n;i++) par[i]=i; } int find(int x) { if(par[x]==x) return x; return par[x]=find(par[x]); } void unite(int x,int y) { int xx=find(x); int yy=find(y); if(xx!=yy) par[xx]=yy; } bool same(int x,int y) { int xx=find(x); int yy=find(y); if(xx!=yy) return false; else return true; } bool cmp(Edge p1,Edge p2) { if(h[p1.v]==h[p2.v]) return p1.w<p2.w; return h[p1.v]>h[p2.v]; } void dfs(int x)///求可达点数量 { for(int j=0;j<a[x].size();j++) { int to=a[x][j].v; if(vis[to]==0){ cnt++; vis[to]++; dfs(to); } } } void Kruskal()///求最小生成树 { init(); sum=0; sort(e+1,e+num+1,cmp); for(int i=1;i<=num;i++) { int u=e[i].u; int v=e[i].v; int w=e[i].w; if(vis[u]==1 && vis[v]==1)///滤去不在最小生成树里的边 { if(!same(u,v)) { sum+=w; unite(u,v); } } } } int main()///P2573 dfs+Kruskal { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&h[i]); num=0; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if(h[u]<h[v])///确保u→v { int temp=v; v=u; u=temp; } a[u].push_back({v,w}); num++; e[num].u=u; e[num].v=v; e[num].w=w; if(h[u]==h[v])///高度相同加反向边 { num++; e[num].u=v; e[num].v=u; e[num].w=w; a[v].push_back({u,w}); } } cnt=1; vis[1]=1; dfs(1); Kruskal(); printf("%d %lld ",cnt,sum); } /** 3 3 3 2 1 1 2 1 2 3 1 1 3 10 3 2 */