链接：https://ac.nowcoder.com/acm/contest/26077/1009
来源：牛客网
题目描述
众所周知，最小生成树是指使图中所有节点连通且边权和最小时的边权子集。 不过最小生成树太简单了，我们现在来思考一个稍微复杂一点的问题。 现在给定一个nnn个点，mmm条边的图，每条边eie_iei都有一个权值wiw_iwi。定义删除一条边eie_iei的代价为wiw_iwi，并且你可以对这个图执行任意次删边操作。 设这个图的最小生成树权值和为sumsumsum，定义一个图的最小生成树是独一无二的当且仅当这个图的边集中没有除最小生成树外的其他子集能满足权值和为sum且使得所有点连通。一个图刚开始可能没有独一无二的最小生成树，现在你可以删除一些边，使得剩下的边的最小生成树大小依然为sumsumsum并且这个图的最小生成树是独一无二的。 现在我们想要知道删除的边的权值和最小是多少？输入描述:
第一行输入为nnn和mmm，表示这个图的点数和边数。 接下来mmm行，每行三个值uiu_iui,viv_ivi,wiw_iwi，分别代表每条边的两个端点和边权。输出描述:
一个整数，代表删除的边的最小权值和。示例1
输入
复制1 0
输出
复制0
备注:
1≤n≤2e51 \leq n\leq 2e51≤n≤2e5
n−1≤m≤2e5n - 1 \leq m\leq 2e5n−1≤m≤2e5
1≤ui,vi≤n1 \leq u_i, v_i \leq n1≤ui,vi≤n
1≤wi≤1e91 \leq w_i \leq1e91≤wi≤1e9
分析
这题是要精简化一张图，使它只能生成唯一一颗最小生成树，且代价最小。
一开始，最小生成树是在印象里是很多集合，然后把它们连在一起，有点想不清楚哪个才是会生成多颗最小生成树的主要原因。
但其实，只要明白，按照kruskal的方式形成的生成树就是最小的。
对于kruskal在形成最小生成树之前的边包括：
第 1 种：有权值相同的点，在使用这个权值前，边的两个端点已经被包含在一个集合内。
第 2 种：有权值相同点，但在使用这个权值前，边的两个端点未被包含在一个集合内。
第 3 种：无权值相同的点，且在使用这个圈之前，边的两个端点已经被包含在一个集合内。
第4种 ：无权值相同的点，且在使用这个圈之前，边的两个端点未被包含在一个集合内
对于形成最小生成树，第1种和第3种是不需要的。
第4种是一定要的。
所以只有第2种需要考虑。
在遍历第二种点的过程中，如果有一些边先将两个点的集合合并，后面的边的端点提前被包含在集合里。那这些边就是多余的。
//-------------------------代码----------------------------
//如果两个点在一个集合上，那不需要管，如果两个点不在一个集合上，取一个就可以了
//#define int ll
const int N = 2e5+10;
int n,m;
struct node {
int a,b,w;
bool operator<(const node &x) const {
return w < x.w;
}
}g[N];
int p[N];
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
void solve()
{
cin>>n>>m;
fo(i,1,n) p[i] = i;
fo(i,1,m) {
int a,b,w;
cin>>a>>b>>w;
g[i] = {a,b,w};
}
sort(g+1,g+1+m);
ll ans = 0;
fo(i,1,m) {
int l,r;l = r = i;
while(r <= m && g[r].w == g[l].w) r ++ ;
fo(k,l,r-1) {
int a = find(g[k].a);
int b = find(g[k].b);
if(a!=b) ans += g[k].w;
}
fo(k,l,r-1) {
int a = find(g[k].a);
int b = find(g[k].b);
if(a!=b) p[a] = b,ans -= g[k].w;
}
i = r - 1;
}
cout<<ans<<endl;
}
void main_init() {}
signed main(){
AC();clapping();TLE;
cout<<fixed<<setprecision(12);
main_init();
// while(cin>>n,n)
// while(cin>>n>>m,n,m)
// int t;cin>>t;while(t -- )
solve();
// {solve(); }
return 0;
}
/*样例区
*/
//------------------------------------------------------------
标签：int,kruskal,最小,Forsaken,leq,1009,权值,集合,生成 From： https://www.cnblogs.com/er007/p/16597246.html