欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

poj 1679

程序员文章站 2022-04-21 20:07:20
题目这题是问你给出的图最小生成树是否唯一。首先我们可以想到,要是最小生成树不唯一,图上与最小生成树相同权值的边,有可能可以替换掉它,这样最小生成树就不唯一了。我们可以枚举这样的边,依次去掉,再重新跑mst,然后看看是否与原mst相等就可以了。#include#include#include#include#include#include<...

题目

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

首先我们可以想到,要是最小生成树不唯一,图上与最小生成树相同权值的边,有可能可以替换掉它,这样最小生成树就不唯一了。我们可以枚举这样的边,依次去掉,再重新跑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

相关标签: 最小生成树