【MST kruskal】 MST Unification CodeForces - 1108F
MST Unification CodeForces - 1108F
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⋅10^5, n−1≤m≤2⋅10 ^5) — 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.
题意
给一个无向加权联通图，没有重边和环。在这个图中可能存在多个最小生成树（MST），你可以进行以下操作：选择某条边使其权值加一，使得MST权值不变且唯一。求最少的操作次数。
思路
- 从MST的构造过程着手。
- 为什么会出现存在多个MST的情况？因为有些边的权值相同，所以在构造MST时，我们可以选择不同的边，构造出不同的MST，但是最后他们的权值和是相同的。
- 要使得MST唯一，就需要使得每一次选择一条边加入MST时，都只有唯一选择。
- 也就是说，在构造过程的某一次抉择中，如果有多条边，他们的权值均最小，且合法（不会构成环，可以加入MST），而且冲突【二者只能选其一，即选择其中一条后，另一条再加进去就会构成环】，那么我们只选择一条加入MST，剩下的冲突边，都权值加一，那么他们就不能再被选到MST里面了。
- 为什么必须强调是冲突边？因为如果不冲突，我们可以先选择一条边权最小的（为w）的边e1加入，下次再选择时，边权最小还是为w，但是现在是边e2了，此时e2由于不会构成环，还是可以加入到MST中。所以实际上它们两个是在同一个方案里的，不够成多种选择。
- 很明显，上面的构造过程是采用了 kruskal算法（即避圈法），我们只需要在构造过程中，统计冲突边的数量，累加起来即可。
AC代码
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 10;
int n, m, fa[maxn];
struct edge
{
int u, v, w;
} e[maxn];
bool cmp(edge a, edge b)
{
return a.w < b.w;
}
void Init()
{
for(int i = 1; i <= n; i++)
fa[i] = i;
}
int Find(int x)
{
return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
void Merge(int x, int y)
{
int fx = Find(x), fy = Find(y);
if(fx != fy)
fa[x] = fy;
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
Init();
for(int i = 0; i < m; i++)
{
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
}
sort(e, e + m, cmp);
int ans = 0;
for(int i = 0; i < m; )
{
int num = 0;
int j = i;
while(e[i].w == e[j].w)//找到边权相同的尾部坐标
j++;
for(int k = i; k < j; k++)//从i到j都是边权最小且相同的边
{
int fx = Find(e[k].u), fy = Find(e[k].v);
if(fx != fy)//统计可以选择的合法边的数量
num++;
}
for(int k = i; k < j; k++)
{
int fx = Find(e[k].u), fy = Find(e[k].v);
if(fx != fy)//从合法边中减去非冲突边(即可以被选入到同一个方案里，不互相冲突的边)
Merge(fx, fy), num--;
}
i = j;
ans += num;//冲突边 = 合法边 - 非冲突边
}
printf("%d\n", ans);
}
return 0;
}