题意： 在一副图中，搞N-1条边，使得每个点都相连， 有多种可能的情况，所以求一种使得其中n-1条边的最大是所有可能的最小，然后并保证连接的n-1条边的权值总和最大 思路： 一开始没有看清题意，随便写了一发“最大生成树”连案例都跑不出，原来还有个条件是有n-1条边中的最大值是所有可能的最小。 然后窝就纳闷了。。。怎么搞法搞到一条最大的最小，随便搞了个最小生成树，写着写着发现其实最小生成树里的最大边，其他生成树就是包含的。 那么找到这条边，跑一下最大生成树就好了； 最小生成树利用并查集比较好~
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL INF=0x3f3f3f3f; const int N=1e5+10; struct asd{ int x,y; LL w; }; asd q[N*4]; bool cmp1(asd a,asd b) { return a.w<b.w; } bool cmp2(asd a,asd b) { return a.w>b.w; } int pre[N]; int m,n; int Find(int x) { int r=x; while(r!=pre[r]) { r=pre[r]; } int i=x,j; while(pre[i]!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) scanf("%d%d%lld",&q[i].x,&q[i].y,&q[i].w); for(int i=1;i<=n;i++) pre[i]=i; sort(q,q+m,cmp1); LL tmax=-INF; int k; for(int i=0;i<m;i++) { int aa=Find(q[i].x); int bb=Find(q[i].y); if(aa!=bb) { pre[aa]=bb; tmax=max(q[i].w,tmax); } } for(int i=0;i<m;i++) { if(q[i].w>tmax) { k=i; break; } } sort(q,q+k,cmp2); LL ans=0; for(int i=1;i<=n;i++) pre[i]=i; for(int i=0;i<k;i++) { int aa=Find(q[i].x); int bb=Find(q[i].y); if(aa!=bb) { pre[aa]=bb; ans+=q[i].w; } } printf("%lld\n",ans); return 0; }