The Unique MST （最小生成树）

72 阅读 0 评论 48 点赞

我是靠谱客的博主无语大炮，最近开发中收集的这篇文章主要介绍The Unique MST （最小生成树），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

plaboy 一格小站

搜索playboy(安全，亲测)

一格小站 – 收藏最全最新的原版pdf英(外)文报刊杂志

///please

题意：

Given a connected undirected graph, tell if its minimum spanning tree is unique.

Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties:
1. V' = V.
2. T is connected and acyclic.

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'.

Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.

Sample

Inputcopy	Outputcopy
2 3 3 1 2 1 2 3 2 3 1 3 4 4 1 2 2 2 3 2 3 4 2 4 1 2	3 Not Unique!

题意：给一棵树，判断是否存在两棵最小生成树

思路：求一遍最小生成树，标记加上的边，最后再求n-1次未包括e[i]的边的最小生成树

记得判断除e[i]的边的最小生成树最后是否有n-1条边

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=107;
const long long Maxx=1e18;
struct Edge{
int x,y,val,flag;
}e[MAXN*MAXN];
int t,n,m,fa[MAXN];
bool cmp(Edge x1,Edge x2){
return x1.val<x2.val;
}
int findfa(int x){
if(fa[x]==x) return x;
return fa[x]=findfa(fa[x]);
}
long long kruskal(int k){
long long res=0;
int Lfa,Rfa,cnt=0;
for(int i=1;i<=m;i++){
if(i==k) continue;
Lfa=findfa(e[i].x);
Rfa=findfa(e[i].y);
if(Lfa!=Rfa){
res+=e[i].val;
fa[Lfa]=Rfa;
cnt++;
}
if(cnt==n-1){
break;
}
}
if(cnt!=n-1)
return Maxx;
else return res;
}
int main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++){
cin>>e[i].x>>e[i].y>>e[i].val;
e[i].flag=1;
}
long long ans=0;
int Lfa,Rfa;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++){
Lfa=findfa(e[i].x);
Rfa=findfa(e[i].y);
if(Lfa!=Rfa){
fa[Lfa]=Rfa;
ans+=e[i].val;
e[i].flag=2;
}
}
long long sum=0,f=1;
for(int i=1;i<=m;i++){
if(e[i].flag==2){
for(int j=1;j<=n;j++)
fa[j]=j;
sum=kruskal(i);
if(sum==ans && ans!=1e18) {
cout<<"Not Unique!"<<"n";
f=0;
break;
}
}
}
if(f) cout<<ans<<"n";
}
}