CodeForces - 1108 F MST Unification【MST最小生成树】

42 阅读 0 评论 28 点赞

我是靠谱客的博主虚幻机器猫，最近开发中收集的这篇文章主要介绍CodeForces - 1108 F MST Unification【MST最小生成树】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

F. MST Unification

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an undirected weighted connected graph with nn vertices and mm edges without loops and multiple edges.

The ii-th edge is ei=(ui,vi,wi)ei=(ui,vi,wi); the distance between vertices uiui and vivi along the edge eiei is wiwi (1≤wi1≤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 11. You canincrease the weight of each edge multiple (possibly, zero) times.

Suppose that the initial MST cost is kk. 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 kk, 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 nn and mm (1≤n≤2⋅105,n−1≤m≤2⋅1051≤n≤2⋅105,n−1≤m≤2⋅105) — the number of vertices and the number of edges in the initial graph.

The next mm lines contain three integers each. The ii-th line contains the description of the ii-th edge eiei. It is denoted by three integers ui,viui,vi and wiwi (1≤ui,vi≤n,ui≠vi,1≤w≤1091≤ui,vi≤n,ui≠vi,1≤w≤109), where uiui and vivi are vertices connected by the ii-th edge and wiwi is the weight of this edge.

It is guaranteed that the given graph doesn't contain loops and multiple edges (i.e. for each ii from 11 to mm ui≠viui≠vi and for each unordered pair of vertices (u,v)(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

input

Copy

output

Copy

input

Copy

output

Copy

input

Copy

output

Copy

input

Copy

output

Copy

input

Copy

1 0

output

Copy

input

Copy

output

Copy

Note

The picture corresponding to the first example:

You can, for example, increase weight of the edge (1,6)(1,6) or (6,3)(6,3) by 11 to unify MST.

The picture corresponding to the last example:

You can, for example, increase weights of edges (1,5)(1,5) and (2,4)(2,4) by 11 to unify MST.

比赛时看了一眼以为是MST上DP，就没管，结果第二天听某位大佬说，其实这就是一道简单题。~~我？？？？？~~

首先我们要让最小生成树的方案数只有1种，并且最小权值是不变的，简单的考虑一下，如果有多种方案数，那么一定是存在若干条相等的边，那么我们就处理这些相等的边就可以了。

想一想Kruskal的原理，就是通过对边进行排序，一条边一条边的放进去，其中会舍弃一些端点已经在MST里的边，若这些边的权值与MST里某条边的权值相等，那么就是我们要求的边。

那么跑Kruskal的时候判一下等边就OK了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include "algorithm"
#include "queue"
#include "unordered_map"
#include "bits/stdc++.h"
#define LOGN 10
#define MAXN (1<<LOGN)
#define MAXNODES 3*( (1<<(2*LOGN)) / 4 + 100)
#define son(x) (p*4-2+x)
using namespace std;
const int mod = 20071027;
struct edge
{
int u,v,w;
bool friend operator < (edge a,edge b)
{
return a.w<b.w;
}
}e[200004];
int fa[200004];
int Find(int a)
{
if(a==fa[a])return a;
else return fa[a]=Find(fa[a]);
}
void init()
{
for (int i = 0; i < 200004; ++i) {
fa[i]=i;
}
}
int main()
{
init();
int n,m;
cin>>n>>m;
int u,v,w;
for (int i = 1; i <= m; ++i) {
//cin>>u>>v>>w;
scanf("%d%d%d",&u,&v,&w);
e[i]={u,v,w};
}
sort(e+1,e+1+m);
int ans=0;
int cnt=0;
for (int i = 1; i <= m; i+=cnt) {
cnt=0;
while(i+cnt<=m&&e[i+cnt].w==e[i].w)//所有与这条边相等并且不在MST上的
{
int fx=Find(e[i+cnt].v),fy=Find(e[cnt+i].u);
ans+=(fx!=fy);
cnt++;
}
cnt=0;
while(i+cnt<=m&&e[i+cnt].w==e[i].w)//要放进MST上的边
{
int fx=Find(e[i+cnt].v),fy=Find(e[i+cnt].u);
if(fx!=fy){
ans--;
fa[fx]=fy;
}
cnt++;
}
}
printf("%dn",ans);
}