poj 1679

题目

这题是问你给出的图最小生成树是否唯一。

首先我们可以想到，要是最小生成树不唯一，图上与最小生成树相同权值的边，有可能可以替换掉它，这样最小生成树就不唯一了。我们可以枚举这样的边，依次去掉，再重新跑mst，然后看看是否与原mst相等就可以了。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
#include<map> 
#include<string>
#include<queue>
#include<stack> 
#include<bitset>
#include<list>
#include<set>
#include<utility>
#include<functional>
#include<iomanip>
#define IO ios::sync_with_stdio(false)
#define eps 1e-7
#define int long long
using namespace std;
int fa[500],n,m,t,flag;
struct node
{
	int u,v,val,eq,del,vis;
	void add(int x,int y,int z)
	{
		u=x,v=y,val=z;
	}
}edge[50005];
bool cmp(node x,node y)
{
	return x.val<y.val;
}
int fin(int x)
{
	if(fa[x]==x)return x;
	else return fa[x]=fin(fa[x]);
}
int kru()
{
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	int k=0,ans=0;
	for(int i=1;i<=m;i++)
	{
		int x=edge[i].u,y=edge[i].v,val=edge[i].val;
		if(edge[i].del==1)continue;
		if(fin(x)!=fin(y))
		{
			if(flag)edge[i].vis=1;
			k++;
			fa[fin(x)]=fin(y);
			ans+=val;
		}
		if(k==n-1)break;
	}
	if(k==n-1)return ans;
	else return 0; 
}
signed main()
{
	IO;
	cin>>t;
	while(t--)
	{
		flag=true;
		cin>>n>>m;
		memset(fa,0,sizeof(fa));
		memset(edge,0,sizeof(edge));
		for(int i=1;i<=m;i++)
		{
			int x,y,z;
			cin>>x>>y>>z;
			edge[i].add(x,y,z);
		}
		sort(edge+1,edge+m+1,cmp);
		int ans1=kru();
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(i==j)continue;
				if(edge[i].val==edge[j].val)
				{
					edge[i].eq=1;
					edge[j].eq=1;
				}
			}
		}
		bool ok=true;
		flag=false;
		for(int i=1;i<=m;i++)
		{
			if(edge[i].eq&&edge[i].vis)
			{
				edge[i].del=1;
				int ans2=kru();
				if(ans1==ans2)
				{
					ok=false;
					break;
				}
				edge[i].del=0;
			}
		}
		if(ok)
		{
			cout<<ans1<<endl;
		}
		else
		{
			cout<<"Not Unique!"<<endl;
		}
	}
}

本文地址：https://blog.csdn.net/qq_37073764/article/details/108848162