本文主要是介绍Codeforces Contest 1108 problem F MST Unification —— 构建唯一最小生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
You are given an undirected weighted connected graph with n vertices and m edges without loops and multiple edges.
The i-th edge is ei=(ui,vi,wi); the distance between vertices ui and vi along the edge ei is wi (1≤wi). The graph is connected, i. e. for any pair of vertices, there is at least one path between them consisting only of edges of the given graph.
A minimum spanning tree (MST) in case of positive weights is a subset of the edges of a connected weighted undirected graph that connects all the vertices together and has minimum total cost among all such subsets (total cost is the sum of costs of chosen edges).
You can modify the given graph. The only operation you can perform is the following: increase the weight of some edge by 1. You can increase the weight of each edge multiple (possibly, zero) times.
Suppose that the initial MST cost is k. Your problem is to increase weights of some edges with minimum possible number of operations in such a way that the cost of MST in the obtained graph remains k, but MST is unique (it means that there is only one way to choose MST in the obtained graph).
Your problem is to calculate the minimum number of operations required to do it.
Input
The first line of the input contains two integers n and m (1≤n≤2⋅105,n−1≤m≤2⋅105) — the number of vertices and the number of edges in the initial graph.
The next m lines contain three integers each. The i-th line contains the description of the i-th edge ei. It is denoted by three integers ui,vi and wi (1≤ui,vi≤n,ui≠vi,1≤w≤109), where ui and vi are vertices connected by the i-th edge and wi is the weight of this edge.
It is guaranteed that the given graph doesn’t contain loops and multiple edges (i.e. for each i from 1 to m ui≠vi and for each unordered pair of vertices (u,v) there is at most one edge connecting this pair of vertices). It is also guaranteed that the given graph is connected.
Output
Print one integer — the minimum number of operations to unify MST of the initial graph without changing the cost of MST.
Examples
inputCopy
8 10
1 2 1
2 3 2
2 4 5
1 4 2
6 3 3
6 1 3
3 5 2
3 7 1
4 8 1
6 2 4
outputCopy
1
inputCopy
4 3
2 1 3
4 3 4
2 4 1
outputCopy
0
inputCopy
3 3
1 2 1
2 3 2
1 3 3
outputCopy
0
inputCopy
3 3
1 2 1
2 3 3
1 3 3
outputCopy
1
inputCopy
1 0
outputCopy
0
inputCopy
5 6
1 2 2
2 3 1
4 5 3
2 4 2
1 4 2
1 5 3
outputCopy
2
题意：
给你一张图，让你增加某些边的值使得最小生成树唯一，输出增加的最小次数。
题解：
如果两个块合并的话，那么肯定是使得这两个块之间的边最小值只有一个，其他的最小值都改变，那么我们排序后每次只对相同的边长的边进行操作，如果这个边的两个点已经在一个并查集内，那么就说明这个边不需要考虑，因为有比他小的边了，之后在插的时候，如果这两个点不在同一个并查集内，就说明这两个块之前没有边相连，–，剩下的就是重复的边了。
#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
const int N=2e5+5;
struct node
{int x,y,w;bool operator< (const node& a)const{return w<a.w;}
}e[N];
int fa[N];
int finds(int x)
{return x==fa[x]?fa[x]:fa[x]=finds(fa[x]);
}
int main()
{//memset(head,-1,sizeof(head));int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)fa[i]=i;int x,y,w;for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);sort(e+1,e+1+m);int ans=0,ne=0,fin=1;for(int i=1;i<=m;){while(fin<=m&&e[fin].w==e[i].w)fin++;int cnt=fin-i;for(int j=i;j<fin;j++)if(finds(e[j].x)==finds(e[j].y))cnt--;for(int j=i;j<fin;j++){if(finds(e[j].x)!=finds(e[j].y))cnt--;fa[finds(e[j].y)]=finds(e[j].x);}i=fin;ans+=cnt;}printf("%d\n",ans);return 0;
}这篇关于Codeforces Contest 1108 problem F MST Unification —— 构建唯一最小生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
