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
上一篇: 【妙解】约瑟夫问题
推荐阅读
-
poj 2689Prime Distance(区间素数)埃氏筛法
-
POJ3252Round Numbers(数位dp)
-
kuangbin专题专题四 Frogger POJ - 2253
-
kuangbin专题 专题一 简单搜索 棋盘问题 POJ - 1321
-
kuangbin专题 专题一 简单搜索 Prime Path POJ - 3126
-
POJ:1017-Packets(贪心+模拟,神烦)
-
poj1637 Sightseeing tour(混合图欧拉回路)
-
POJ1862 Stripies 贪心 B
-
POJ2431 优先队列+贪心 - biaobiao88
-
POJ3233Matrix Power Series(矩阵快速幂)