题目描述
给定一个无向连通图，包含 \(N\) 个顶点和 \(M\) 条边。每条边有一个权值 \(V\)。需要找到一个生成树，满足以下条件：
- 最大边权值尽可能小：生成树中所有边的权值最大值在所有可能的生成树中是最小的。
- 总边权值和尽可能大：在满足条件 1 的前提下，生成树的所有边的权值之和尽可能大。
输出满足条件的生成树的总边权值和。
输入格式
第一行输入两个正整数 \(N\) 和 \(M\)，分别表示顶点数和边数。
- \(1 \leq N \leq 10^5\)
- \(1 \leq M \leq 2 \times 10^5\)
接下来 \(M\) 行，每行三个整数 \(A\)、\(B\)、\(V\)，表示顶点 \(A\) 和顶点 \(B\) 之间有一条权值为 \(V\) 的无向边。
- \(1 \leq A, B \leq N\)
- 权值 \(V\) 的范围为 int 范围内的整数（可能为负数）
输入数据保证图是连通的。
输出格式
输出一个整数 \(R\)，表示满足条件的生成树的边权值总和。
输入样例
4 5
1 2 2
1 3 5
2 3 3
2 4 2
3 4 5
输出样例
9
算法
-
先满足：最大边最小：按边权升序排序，运行 Kruskal 算法构建最小生成树。记录使得图第一次连通的那条边的权值，记为
limit。这就是最小可能的最大边权值。 -
可用边：收集所有权值 ≤
limit的边。 -
再满足：总边权值最大的生成树。 将这些可用边按权值降序排序，再次运行 Kruskal 构建生成树。
#include <bits/stdc++.h>
using namespace std;
int n,m,Fa[100002];
struct node{int x,y,v;bool operator<(const node &T)const{return v<T.v;}
}edge[200002];
bool cmp(node &T1,node &T2) {return T1.v>T2.v;
}
int GetFa(int k) {if (k==Fa[k]) return k;return Fa[k]=GetFa(Fa[k]);
}
int main(){cin>>n>>m;for (int i=1;i<=m;i++)scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].v);sort(edge+1,edge+1+m);int k=1;int cnt=1;for (int i=1;i<=n;i++) Fa[i]=i;for (;k<=m;k++) {int fx,fy;fx=GetFa(edge[k].x);fy=GetFa(edge[k].y);if (fx!=fy) {cnt++;Fa[fy]=fx;if (cnt==n) break;}}while (k<m && edge[k].v==edge[k+1].v) k++;sort(edge+1,edge+1+k,cmp);for (int i=1;i<=n;i++) Fa[i]=i;long long Ans=0;cnt=1;for (int i=1;i<=k;i++) {int fx,fy;fx=GetFa(edge[i].x);fy=GetFa(edge[i].y);if (fx!=fy) {cnt++;Fa[fy]=fx; Ans+=edge[i].v;if (cnt==n) break;}}cout<<Ans<<endl;return 0;
}