poj1679 The Unique MST（最小生成树唯一性）

最小生成树的唯一性，部分参考了oi-wiki

如果一条不在最小生成树边集内的边，它可以替换一条在最小生成树边集内，且权值相等的边，那么最小生成树不是唯一的

同过kruskal来判断

考虑权值相等的边，记录有几条边是目前可以被选入的，和实际选入了几条边，如果不相同，则最小生成树不唯一

原因是如果出现这两个值不相等的情况，则一定出现了环，且这个环内至少有两条边权值相同

具体实现，用一个\(\text{tail}\)指针指向当前权值的最后一条边，当\(\text{i}>\text{tail}\)（也就是当前边权的边全部被考虑完）的时候，就去判断上述的两个值是否相等

注意kruskal循环的时候要循环到\(m+1\)，这样如果权值最大的一部分边要被选到的话，会在\(i=m+1\)的时候进行判断

而且在判断当前选的边数已经等于\(n-1\)，不能直接跳出，要等到\(\text{i}>\text{tail}\)判断那两个值是否相等，如果相等再跳出，否则也是不唯一

当然网上也有那种每次删边跑kruskal的做法，但复杂度明显没有这个优秀

模板题

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	int x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

int n,m;

struct data{

	int from,to,w;

}e[10006];

int fa[10006];

inline int cmp(data aa,data aaa){return aa.w<aaa.w;}

inline int find(int k){return k==fa[k]?k:fa[k]=find(fa[k]);}

int main(){int t=read();while(t--){

	n=read();m=read();

	for(reg int i=1;i<=n;i++) fa[i]=i;

	for(reg int i=1;i<=m;i++){

		e[i].from=read();e[i].to=read();e[i].w=read();

	}

	std::sort(e+1,e+1+m,cmp);

	int ans=0,cnt=1,tail=0;

	int choose=0,sum=0;

	for(reg int i=1;i<=m+1;i++){

		if(i>tail){

//				std::printf("%d %d\n",choose,sum);

			if(choose!=sum) goto NOT;

			if(cnt>=n) break;

			sum=choose=0;

			for(tail++;e[tail].w==e[i].w&&tail<=m;tail++)

				if(find(e[tail].from)!=find(e[tail].to)) sum++;//如果这条边目前能被加进去，sum才+1

			tail--;

		}

		int from=find(e[i].from),to=find(e[i].to);

		if(from==to) continue;

		cnt++;fa[from]=to;

		if(cnt<=n) ans+=e[i].w,choose++;;

	}

	std::printf("%d\n",ans);continue;

	NOT:;std::puts("Not Unique!");

}

	return 0;

}

巴特西

poj1679 The Unique MST（最小生成树唯一性）

最新文章

热门文章