CF1108F MST Unification

本文主要是介绍CF1108F MST Unification，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面

给定一个有n个点，m条边的无向连通图，每条边有边权。 定义一次操作为：选择一条图中的边，并将其权值+1。
试求最小的操作次数，使得操作后的图的最小生成树是唯一的。

题解

首先我们要认识到一点，我们只可能对可行边进行操作，因为必须边不影响最小生成树的唯一性，不可能在最小生成树上的边本来就不影响最小生成树。
那么我们如何判断可行边？
假设我们已经有了一个最小生成树，那么原边集中一条什么样的边，才可以替换掉原树中的一条边？
那必然是连上新边后，在最小生成树中形成的环上，有与它边权相同的边。
这样的话，我们就可以断开那条边权相同的边，连上这条新边，获得一个新的最小生成树。
我们如何把一个可行边变成一个不能在最小生成树上的边。
注意到这条新边必然是环上最大的边（可能是之一），因为如果环上有边大于它的话，它在第一次建立最小生成树的时候就应该被加入，而不是作为一个可行替补加进来。
因此，我们只要对这条新边边权加一，那么环上就不可能有与之边权一致的边，那我们就成功的将一个最小生成树可行边变成了一条不在最小生成树上的边。

接下来考虑如何统计答案。
如果一条边可以连接2个不同连通块，那么这条边对答案没有贡献，但是在加入这条边后，后面加入的原本可以连接这2个连通块，且与之权值相同的边都对答案有贡献。

所以我们可以边做kruskal边统计答案。
因为加入一条边后，不好判断它后面与之权值相同的边是不是连接了2个在当前权值之前未被连接的联通块，
所以我们每次处理一个权值的边的时候，我们在所有当前权值边连接之前，先假设所有连接2个不同连通块的边都对答案有贡献。
然后我们在实际连边的时候，去掉实际连边的边数即可。

#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 200100

int n, m, ans;
int fa[AC];
struct node{
	int x, y, w;
}way[AC];

bool cmp(node a, node b){return a.w < b.w;}

inline int read()
{
	int x = 0; char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x;
}

void pre()
{
	n = read(), m = read();
	for(R i = 1; i <= n; i ++) fa[i] = i;
	for(R i = 1; i <= m; i ++)
		way[i].x = read(), way[i].y = read(), way[i].w = read();
	sort(way + 1, way + m + 1, cmp);
}

int find(int x)
{
	if(fa[x] != x) return fa[x] = find(fa[x]);
	else return x;
}

void work()
{
	//for(R i = 1; i <= m; i ++) printf("%d %d %d\n", way[i].x, way[i].y, way[i].w);
	int j;
	for(R i = 1; i <= m; i = j + 1)
	{

		j = i;
		for( ; way[j].w == way[i].w; j ++)
			if(find(way[j].x) != find(way[j].y)) ans ++;
		-- j;
	//	printf("%d %d\n", i, ans);
		for(R k = i; k <= j; k ++)
		{
			int u = find(way[k].x), v = find(way[k].y);
			if(u != v) ans --, fa[v] = u;//减去不需要加的
		}
	//	printf("%d %d\n", i, ans);
	}
	printf("%d\n", ans);
}

int main()
{
//	freopen("in.in", "r", stdin);
	pre();
	work();
	return 0;
}

这篇关于CF1108F MST Unification的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！