The Unique MST
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 17881 | Accepted: 6204 |
Description
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.
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!
次小生成树：首先必须存在最小生成树，次小生成树的意思就是，除了最小生成树之外，存在一个生成树，权值仅大于最小生成树，也就是
给出一个带边权的无向图G，设其最小生成树为T，求出图G的与T不完全相同的边权和最小的生成树（即G的次小生成树）。一个无向图的两棵生成树不完全相同，当且仅当这两棵树中至少有一条边不同。（注意，图G可能不连通，可能有平行边）
那么如何来求最小生成树？
定义生成树T的一个可行变换(-E1, +E2)：将T中的边E1删除后，再加入边E2（满足边E2原来不在T中但在G中），若得到的仍然是图G的一棵生成树，则该变换为可行变换，该可行变换的代价为(E2权值 - E1权值)。这样，很容易证明，G的次小生成树就是由G的最小生成树经过一个代价最小的可行变换得到。进一步可以发现，这个代价最小的可行变换中加入的边E2的两端点如果为V1和V2，那么E1一定是原来最小生成树中从V1到V2的路径上的权值最大的边。
算法：
1.设立数组F，F[x][y]表示T中从x到y路径上的最大边的权值。F数组可以在用Prim算法求最小生成树的过程中得出。
2.每次将边(i,j) G[i][j]加入后（j是新加入的边的新端点），枚举树中原有的每个点k（包括i，但不包括j），则F[k][j]=max{F[k][i],G[i][j]}，又由于F数组是对称的，可以得到F[j][k]=F[k][j]。
3.将图G中的边(i, j)删除（就是将邻接矩阵中(i,j)边权值改为∞）！因为T中的边是不能被加入的。
4.等T被求出后，所有的F值也求出了，然后，枚举点i、j，若邻接矩阵中边(i, j)权值不是无穷大（这说明i、j间存在不在T中的边），则求出{(i, j)边权值 - F[i][j]}的值，即为加入边(i, j)的代价，求最小的总代价即可。
!!! 另外注意三种特殊情况：
【1】图G不连通，此时最小生成树和次小生成树均不存在。判定方法：在扩展T的过程中找不到新的可以加入的边；【2】图G本身就是一棵树，此时最小生成树存在（就是G本身）但次小生成树不存在。判定方法：在成功求出T后，发现邻接矩阵中的值全部是无穷大；
【3】图G存在平行边。这种情况最麻烦，因为这时代价最小的可行变换(-E1, +E2)中，E1和E2可能是平行边！因此，只有建立两个邻接矩阵，分别存储每两点间权值最小的边和权值次小的边的权值，然后，每当一条新边(i, j)加入时，不是将邻接矩阵中边(i, j)权值改为无穷大，而是改为连接点i、j的权值次小的边的权值
int G[N][N] //邻接矩阵
int f[N][N] //最小生成树中每两点间的最大边的权值
bool vis[N] // 标记点
int p[N] //存放最小生成树过程的加入点集合
/**********************
# 2013-8-21 21:28:04
# Time: 16MS Memory: 260K
# Author: zyh
# Status: Accepted
**********************/
#define INF 99999999
#define N 110
#define MAX(a,b) (a)>(b)?(a):(b)
#include<stdio.h>
#include<string.h>
int n,G[N][N],f[N][N];
void prim()
{
int p[N],vis[N],i,j,v,sum,k;
memset(vis,0,sizeof(vis));
memset(f,0,sizeof(f));
k=0;
p[k++] = 1;//存放最小生成树点集合
vis[1] = 1;
sum = 0;
for(int t=1;t<n;t++){ // n个顶点，n-1条边，循环n-1次，每次加入一条新的边
int min = INF;
int s,e;
for(j=0;j<k;j++){//枚举书中已有的每个点
v = p[j];
for(i=1;i<=n;i++){ //寻找点v相连的最小边；
if(!vis[i]&& G[v][i]<min){
min = G[v][i];
s = v; e = i;//记录新加入边的两端点
}
}
}
for(j=0; j<k;j++){ //找到要新加入的边，
v = p[j];
f[e][v] = f[v][e] = MAX(f[v][s],G[s][e]);
}
G[s][e] = G[e][s] = INF; //INF 代表该边已被删除
p[k++] = e;//加入新结点
vis[e] = 1; //标记
sum += min; //求最小生成树的权值
}
/********判断是否存在次小生成树，或者最小生成树是否唯一 ********/
int flag = 1; //标记是否有次小生成树
int sign = 0; //标记是否所有的边都在最小生成树中 0代表是， 1代表不是
for(i=1;i<=n;i++){ //枚举图中剩余的不在最小生成树的边
for(j=1;j<=n;j++){
if(G[i][j]!=INF){ //存在图中不在最小生成树的边
sign = 1; //标记还存在其他边
if(i!=j && G[i][j]!=f[i][j]) {
flag = 0;
}
}
}
}
if(flag && sign) printf("Not Unique!\n"); //
else printf("%d\n",sum);
}
int main()
{
int t,m,i,j,a,b,c;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
G[i][j] = INF;
}
while(m--){
scanf("%d%d%d",&a,&b,&c);
G[a][b] = G[b][a] = c;
}
prim();
}
return 0;
}
/*
9
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 3
1 2 2
2 3 3
3 1 3
3 3
1 2 3
2 3 2
3 1 3
3 2
1 2 2
2 3 2
*/