The Unique MST （次小生成数）

39 阅读 0 评论 26 点赞

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

概述

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 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!

题意：

给你一个有权值的无相图，判断最小生成树是否唯一。
首先，我们可以通过prim算法得到一组样例的最小生成树。之后，我们通过某些操作就可以判断这组最小生成树是否唯一。

整体思想就是，先得到最小生成树。然后，我们可以在最小生成树外选择一条边加入其中，这时，必然会形成一个环，那么我们就在最小生成树上删去一条边（不能是加入的边），

这样，我们就得到了另一个最小生成树。如果这个最小生成树的权值之和和原来的最小生成树权值相同，就说明该组样例的最小生成树不唯一。

算法实现流程：

1.首先使用prim算法为基础，在此基础上加入数组max1[i][j],用于记录i到j路径上的权值最大的边。

2.加入stack[i]数组，用于记录加入到MST中的顶点

3.加入pre[i]数组，用于记录加入MST的顶点的相关联边的直接前驱。

4.在找到temp和k后，需要进行一次循环，用于更新新加入点到MST各点路径最大值（作用在于，如果我要在这个顶点加边形成环，我需要去掉这个环上权值最大的边）至于为什么要用

max(max1[stack[j]][pre[k]], temp)

比较的是pre[k]，因为加入的k点如果要跟MST其他点连接，必须通过它的直接前驱，而它的前驱一定是MST中已经确定的到各个顶点都是最大值的记忆化状态，所以我们要比较的是pre[k]，而后面之所以是temp因为，temp是MST和非MST两个集合相连的最小权值的边，但是你要加入MST，不能保证他是MST中权值最小的（甚至是最大的）所以加入时需要用temp和max1[stack[j][pre[k]]比较，来得到max1[i][j]（i到j路径上权值最大的边）

5.保存一下加入到MST中的顶点

6.更新lowxost，并且记录下更新后的直接前驱

7.prim算法结束后，max1数组存放的就是MST中各个顶点之间的权值最大的边。这时，我们需要对MST外的边加入到MST中并删除最大边的操作。这时候我们需要一个双层循环，遍历每一个MST外的边，当然，必须保证是MST外的边，那个判断语句就是防止是MST种的边，至于为什么i != pre[j] 和 j != pre[i]同时存在，是为了防止出现i=3，j=2和j=2，i=3,这种情况。这个判断一定要正确，要不然就会出现错误。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
#define N 510
int inf = 99999999;
int map[N][N], lowcost[N], pre[N], stack[N], max1[N][N];
//数组max1[i][j],用于记录i到j路径上的权值最大的边
bool visit[N];
int n, m, sum;
void prim() //默认1在MST中
{
int temp, k;
int top; //保存最小生成树的结点
int i,j;
memset(visit, false, sizeof(visit)); //初始化
visit[1] = true;
sum = 0;
top = 0;
for(i = 1; i <= n; ++i)
{
pre[i] = 1;//加入pre[i]数组，用于记录加入MST的顶点的相关联边的直接前驱。
lowcost[i] = map[1][i];
}
lowcost[1] = 0;
stack[top++] = 1; //加入stack[i]数组，用于记录加入到MST中的顶点
for(i = 1; i <= n; ++i)
{
temp = inf;
for(j = 1; j <= n; ++j)
if(!visit[j] && temp > lowcost[j])
temp = lowcost[k = j];
if(temp == INT_MAX)
break;
visit[k] = true;
sum += temp;
for(j = 0; j < top; ++j) //新加入点到MST各点路径最大值
max1[stack[j]][k] = max1[k][stack[j]] = max(max1[stack[j]][pre[k]], temp);
stack[top++] = k; //保存MST的结点
for(int j = 1; j <= n; ++j) //更新
if(!visit[j] && lowcost[j] > map[k][j])
{
lowcost[j] = map[k][j];
pre[j] = k; //记录直接前驱
}
}
}
int main()
{
int i,j,T;
int start, end, cost;
int minn;
scanf("%d", &T);
while(T --)
{
sum = 0;
for(i = 1; i < N; ++i)
for(j = 1; j < N; ++j)
{
map[i][j] = inf;
max1[i][j] = 0;
}
scanf("%d%d", &n, &m);
for(i = 1; i <= m; ++i)
{
scanf("%d%d%d", &start, &end, &cost);
map[start][end] = map[end][start] = cost;
}
prim();
minn = inf;
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
if(i != j && i != pre[j] && j != pre[i]) //枚举MST以外的边
minn = min(minn, map[i][j] - max1[i][j]); //求出{MST外加入边-MST环上权值最大边}最小值
if(minn != 0)
printf("%dn",sum);
else
printf("Not Unique!n");
}
return 0;
}