# POJ1679 The Unique MST（次小生成树）

## The Unique MST

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 34321 Accepted: 12513

### 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.

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

### Source

POJ Monthly--2004.06.27 srbga@POJ

### 链接

http://poj.org/problem?id=1679

### 代码

StatusAccepted
Memory240kB
Length2130
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
int G[maxn][maxn];
int Max[maxn][maxn];
bool used[maxn][maxn];
bool vis[maxn];
int pre[maxn];
int lowc[maxn];
int n, m;

int Prim() // 求得最小生成树
{
int ans = 0;
memset(vis, 0, sizeof(vis));
memset(Max, 0, sizeof(Max));
memset(used, 0, sizeof(used));
vis[1] = true;
pre[1] = -1;
lowc[1] = 0;
for (int i = 2; i <= n; ++i)
{
lowc[i] = G[1][i];
pre[i] = 1;
}
for (int i = 2; i <= n; ++i)
{
int minc = inf, p = -1;
for (int j = 1; j <= n; ++j)
{
if (!vis[j] && minc > lowc[j])
{
minc = lowc[j];
p = j;
}
}
if (minc == inf) // 不存在最小生成树
return -1;
ans += minc;
vis[p] = true;
used[p][pre[p]] = used[pre[p]][p] = true;
for (int j = 1; j <= n; ++j)
{
if (vis[j] && j != p)
Max[j][p] = Max[p][j] = max(Max[j][pre[p]], lowc[p]); // 最小瓶颈路
if (!vis[j] && lowc[j] > G[p][j])
{
lowc[j] = G[p][j];
pre[j] = p;
}
}
}
return ans;
}

int smst(int tmp)
{
int ans = inf;
for (int i = 1; i <= n; ++i) // 遍历不在最小生成树中的边
{
for (int j = 1; j <= n; ++j)
{
if (!used[i][j] && i != j)
ans = min(ans, tmp + G[i][j] - Max[i][j]);
}
}
if (ans == inf)
return -1;
return ans;
}

int main()
{
int T, u, v, w;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
G[i][j] = ((i == j) ? 0 : inf);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
G[u][v] = G[v][u] = w;
}
int ans1 = Prim(), ans2 = smst(ans1);
if (ans1 == ans2 || ans1 == -1) // 判断是否相等
printf("Not Unique!\n");
else
printf("%d\n", ans1);
}
return 0;
}

The end.
2018-05-11 星期五