链接：https://ac.nowcoder.com/acm/contest/1221/H 来源：牛客网 题意：大致上是说有一个图，告知你多少点多少边每条边权值多少，要你减去一些边，使得剩余的图的最小生成树唯一，求减去的边的权值最小是多少。
思路：最小生成树不唯一的原因只可能是有多条权值相同的边，使得构造树时有多种选择，于是我们就要把边先按权值从小到大排序。然后每组权值相同的边，先进行一次遍历，若是一条边左右两点不在已经生成的树中，就把它的权值全部加到要删除的权值del中，若在就不操作，这是因为现在的树是最小的，若在树中就不会对结果有影响；然后再进行一次遍历，这一次若是边两点不在已经生成的树中，然后让利用parent数组把这两点放进最小生成树里，让del减去它的权值，因为最小生成树中的边不能剪掉，这样子就可以把所有多余的在当前情况下的权值最小的边去掉。
#include<iostream> #include<algorithm> using namespace std; int parent[200010]; typedef struct { int u; int v; int w; }graphs; graphs gra[200010]; bool cmp(graphs a,graphs b) { return a.w<b.w; } int findparent(int x) { return x==parent[x] ? x : parent[x]=findparent(parent[x]); } int main() { int n,m; cin>>n>>m; for(int i=0;i<n;i++)parent[i]=i; for(int i=0;i<m;i++) { cin>>gra[i].u>>gra[i].v>>gra[i].w; } sort(gra,gra+m,cmp); long long del=0; for(int i=0;i<m;) { int lastmin=i,w=gra[i].w; while(lastmin<m&&gra[lastmin].w==w)lastmin++; for(int j=i;j<lastmin;j++) { int u_p,v_p; u_p=findparent(gra[j].u); v_p=findparent(gra[j].v); if(u_p!=v_p)del+=w; } for(int j=i;j<lastmin;j++) { int u_p,v_p; u_p=findparent(gra[j].u); v_p=findparent(gra[j].v); if(u_p!=v_p) { del-=w; parent[u_p]=v_p; } } i=lastmin; } cout<<del<<endl; return 0; }