题解:其实看到这句话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; }