题解 | #Forsaken喜欢独一无二的树#

题意

删除一些边，使得最小生成树唯一，问删除的边的权值和最小是多少？

思路

为什么最小生成树不唯一：因为连接相同两个集合的边，权值相同的可能有多个
所以，我们只需要删除 权重相同的 且 连接同两个集合的 那些边即可 ：这些边中留一个 用于维持最小生成树，其余的均删掉。

因为是 稀疏图，所以使用 Kruskal , 在里面进行操作即可

关于在 Krustral 中 res 先加 w 后来再 减 w 的解释：
加：为了保证最小生成树唯一，假设权值相同的这一波边都必须删除
为什么 a == b 的不删： a == b 说明在前几波 权重相同的边中，a 所在集合 和 b 所在集合 已经连接，此时这一波边的权值和前面出现过的几波权值 肯定不同，所以该边留下 不会影响最小生成树的唯一性，故不删

减：减去的是 维持最小生成树所必须的边

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+10;

struct node{
    int a,b,w;
}edges[N];
int p[N];
int n,m;

bool cmp(node x,node y){
    return x.w<y.w;
}

int find(int x){
    if(x==p[x]) return x;
    return p[x]=find(p[x]);
}

ll Kruskal_change(){
    ll res=0;
    for(int i=0;i<m;) {
        int j=i;
        for(;j<m;j++) if(edges[i].w!=edges[j].w) break;  // 求 j 

        for(int id=i;id<j;id++){  // 遍历这一波 权值相同的边
            int a=edges[id].a,b=edges[id].b,w=edges[id].w;
            a=find(a),b=find(b);
            if(a!=b) res+=w;  //在此处 a==b 的说明，之前已经被连过
        }

        for(int id=i;id<j;id++){
            int a=edges[id].a,b=edges[id].b,w=edges[id].w;
            a=find(a),b=find(b);
            if(a!=b)   res-=w,p[a]=b;
        }
        // res先加w，再减去w的解释：
        i=j;
    }
    return res;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }

    sort(edges,edges+m,cmp);
    for(int i=1;i<=n;i++) p[i]=i;

    ll t=Kruskal_change();
    cout<<t<<endl;

    return 0;
}