Description
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
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
Sample Input
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
Sample Output
3
Not Unique!
题意：问最小生成树是否唯一。
分析：求次小生成树，推断次小生成树和最小生成树是否相等。
求次小生成树的步骤：
(1)先用Prime求出最小生成树MST，在Prime的同一时候用一个矩阵mmax[ ][ ]记录在MST中连接随意两点u,v的唯一路径中权
值最大的那条边的权值。做法：Prime是每次添加一个节点t。用该点新加入MST的边与它前一个加入MST的点的mmax的值做比较。
(2)枚举最小生成树以外的边，并删除该边所在环上权值最大的边。
(3)取得的全部生成树中权值最小的一棵即为所求。
算法的时间复杂度为O(n^2)。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 111
#define inf 0x3f3f3f3f int map[maxn][maxn],mmax[maxn][maxn];//map邻接矩阵存图,mmax示最小生成树中i到j的最大边权
bool used[maxn][maxn];//判断该边是否加入最小生成树
int pre[maxn],dis[maxn];//pre用于mmax的构建，装前一个放入MST的结点，dis用于构建MST void init(int n)
{
for (int i=;i<=n;i++)//图初始化
{
for (int j=;j<=n;j++)
{
if (i==j)
{
map[i][j]=;
}
else
{
map[i][j]=inf;
}
}
}
} void read(int m)
{
int u,v,w;
for (int i=;i<m;i++)//读入图
{
scanf("%d%d%d",&u,&v,&w);
map[u][v]=map[v][u]=w;
}
}
int prime(int n)//构建MST
{
int ans=;
bool vis[maxn];
memset(vis,false,sizeof(vis));
memset(used,false,sizeof(used));
memset(mmax,,sizeof(mmax));
for (int i=;i<=n;i++)
{
dis[i]=map[][i];
pre[i]=;//1点为第一个放入MST的点，先设为所有点的前驱结点
}
pre[]=;
dis[]=;
vis[]=true;
for (int i=;i<=n;i++)
{
int min_dis=inf,k;
for (int j=;j<=n;j++)
{
if (vis[j]==&&min_dis>dis[j])
{
min_dis=dis[j];
k=j;
}
}
if (min_dis==inf)//如果不存在最小生成树
{
return -;
}
ans+=min_dis;
vis[k]=true;
used[k][pre[k]]=used[pre[k]][k]=true;//标记为放入MST的点
for (int j=;j<=n;j++)
{
if (vis[j])
{
mmax[j][k]=mmax[k][j]=max(mmax[j][pre[k]],dis[k]);//最小生成树环的最大边
}
if (!vis[j]&&dis[j]>map[k][j])
{
dis[j]=map[k][j];
pre[j]=k;
}
}
}
return ans;//最小生成树的权值之和
}
int smst(int n,int min_ans)//min_ans 是最小生成树的权值和
{
int ans=inf;
for (int i=;i<=n;i++)//枚举最小生成树之外的边
{
for (int j=i+;j<=n;j++)
{
if (map[i][j]!=inf&&!used[i][j])
{
ans=min(ans,min_ans+map[i][j]-mmax[i][j]);//该边次小MST的权值为MST加上该边再减去该边所在环的最大MST边
}
}
}
if (ans==inf)
{
return -;
}
return ans;
}
void solve(int n)
{
int ans=prime(n);
if (ans==-)
{
puts("Not Unique!");
return;
}
if (smst(n,ans)==ans)//次小MST权值等于MST说明MST不唯一
{
printf("Not Unique!\n");
}
else
{
printf("%d\n",ans);
}
}
int main()
{
int t,n,m; scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
init(n);
read(m);
solve(n);
} return ;
}