The Unique MST(POJ 1679)---次小生成树模板题题目描述输入格式输出格式输入样例输出样例分析源程序

75 阅读 0 评论 50 点赞

我是靠谱客的博主无奈乐曲，最近开发中收集的这篇文章主要介绍The Unique MST(POJ 1679)---次小生成树模板题题目描述输入格式输出格式输入样例输出样例分析源程序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

题目描述

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:

V’ = V.
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’.

输入格式

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.

输出格式

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

输入样例

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!

分析

题目大意是对于t组测试，每组测试给出n个点m条边的无向图，求无向图中的最小生成树是否唯一。

对于这道题，显然我们要知道次小生成树的大小，如果次小生成树恰好等于最小生成树，则不唯一输出“Not Unique!”；若次小生成树大于最小生成树，则输出最小生成树的大小。那么怎么求次小生成树呢？原理如下：

首先，我们知道对于一颗最小生成树，我们任意加进一条边<u,v>都会形成一个环，那么为了保持他的树的形状和连通性，我们显然需要删除环路中的一条边，而要使得对于多种删边情况，必定是删除环路中权值最大边后的生成树最小，如图：

显然，对于加入的边<C,D>，我们删除权值为5的边<D,E>的情况生成树最小。
那么对于求次小生成树，我们可以在找到最小生成树后，枚举每一条非树边并将其加入到最小生成树中，求其中的最小值，即次小生成树的大小。
考虑到在枚举过程中，我们要找到边<u,v>两点间的最大边权值dis[u][v]，而在最差情况下即完全图中，我们需要知道任意两点间的最大距离，所以我们需要用动态规划的思想，通过状态转移方程式dis[u][v]=max(dis[u][pre[v]]，w<u,v>)，pre[v]是u的父节点，这样对于每个dis[u][v]只需常数时间计算，总时间复杂度为O(n^2)。

以下是分别用prim算法和Kruskal算法求次小生成树的源代码：

源程序

Prim算法

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 105
#define MAXM MAXN*MAXN
#define INF 0x3f3f3f3f
using namespace std;
struct Edge{
int v,w;
bool operator <(const Edge a)const{
return w>a.w;
}
};
int t,n,m,g[MAXN][MAXN];
int dis[MAXN],pre[MAXN],dp[MAXN][MAXN];
bool vis[MAXN],connect[MAXN][MAXN];
int prim()
{
priority_queue<Edge> q;
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
memset(dp,0,sizeof(dp));
dis[1]=0,vis[1]=true;
for(int i=1;i<=n;i++)
if(g[1][i]!=INF){
dis[i]=g[1][i],pre[i]=1;
q.push(Edge{i,g[1][i]});
}
while(!q.empty()){
int u=q.top().v,w=q.top().w;q.pop();
if(vis[u])continue;
vis[u]=true;
connect[u][pre[u]]=connect[pre[u]][u]=false;	//标记边 
dp[u][pre[u]]=dp[pre[u]][u]=w;	//更新最大值 
for(int v=1;v<=n;v++){
if(v!=u && vis[v]){	//更新树中节点 
dp[u][v]=dp[v][u]=max(dp[pre[u]][v],dis[u]);
}
if(!vis[v] && dis[v]>g[u][v]){	//更新非树中节点 
dis[v]=g[u][v],pre[v]=u;
q.push(Edge{v,dis[v]});
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans+=dis[i];
return ans;
}
int main()
{
scanf("%d",&t);
while(t--){
memset(g,0x3f,sizeof(g));
memset(connect,false,sizeof(connect));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u][v]=g[v][u]=w;
connect[u][v]=connect[v][u]=true;
}
int add=INF;	//最小增量 
int res=prim();	//求最小生成树 
bool flag=true;
for(int i=1;i<=n&&flag;i++){	//枚举点 
for(int j=i+1;j<=n;j++){	//枚举边 
if(connect[i][j]==false)
continue;
if(g[i][j]-dp[i][j]<add)
add=g[i][j]-dp[i][j];
if(add==0){	//恰好等于最小生成树 
flag=false;
break;
}
}
}
if(!flag)
printf("Not Unique!n");
else
printf("%dn",res);
}
}

Kruskal算法

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define MAXN 105
#define MAXM MAXN*MAXN
#define INF 0x3f3f3f3f
using namespace std;
struct Edge{
int u,v,w,id;
bool operator <(const Edge a)const{
return w>a.w;
}
Edge(){}
Edge(int u,int v,int w,int id):u(u),v(v),w(w),id(id){}
}edge[MAXM];
int t,n,m,father[MAXN],dp[MAXN][MAXN];
bool connect[MAXM];
vector<int> g[MAXN];
priority_queue<Edge> q;
void init()
{
memset(connect,false,sizeof(connect));
memset(dp,0,sizeof(dp));
while(!q.empty())q.pop();
for(int i=1;i<=n;i++){
father[i]=i;
g[i].clear();
g[i].push_back(i);
}
}
int find(int x)
{
if(x==father[x]) return x;
return father[x]=find(father[x]);
}
int kruskal()
{
int res=0,k=0;
while(k<n-1){
int u=q.top().u,v=q.top().v,w=q.top().w,id=q.top().id;
int fu=find(u),fv=find(v);
q.pop();
if(fu!=fv){	//两者不连通，更新 
res+=w;
k++;
connect[id]=true;
father[fu]=fv;
int fulen=g[fu].size(),fvlen=g[fv].size();
for(int i=0;i<fulen;i++)	//更新两点间最大值 
for(int j=0;j<fvlen;j++)
dp[g[fu][i]][g[fv][j]]=dp[g[fv][j]][g[fu][i]]=w;
for(int i=0;i<fulen;i++)
g[fv].push_back(g[fu][i]);
}
}
return res;
}
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
edge[i].id=i;
q.push(edge[i]);
}
int add=INF;	//最小增量 
int res=kruskal();	//最小生成树
bool flag=true;
for(int i=1;i<=m&&flag;i++){
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
if(!connect[i]){	//非树边 
if(w-dp[u][v]<add)
add=w-dp[u][v];
if(add==0){
flag=false;
break;
}
}
}
if(!flag)
printf("Not Unique!n");
else
printf("%dn",res);
}
}