POJ1679 The Unique MS（次小生成树）

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!

题意

问最小生成树是否唯一，如果唯一，输出边长和，如果不唯一，输出not unique。

分析

其实这是一个裸的次小生成树问题。
怎么求次小生成树呢？我们都要先求出最小生成树，考虑不在树上的边，它必然与树上的边形成一个环。我们只需要用这条边取代环上的最大边就可以了。在这道题中，我们只需要判断这条边与环上最大边是否相等就可以了。
一般来讲，次小生成树有两种做法，一种复杂度是 $O(n^2+mlogm)$O(n2+mlogm)，另一种是 $O(mlogn+mlogm)$O(mlogn+mlogm)。

先讲讲第一种。

我们求出最小生成树后，在树上跑一遍dp。记 $f\left[i\right]\left[j\right]$f[i][j] 表示 $i$i 到 $j$j 在树上的路径的最大边， $v\left[i\right]$v[i] 表示 $i$i 点是否访问过。
转移方程为
$if\left(v\right[j\left]\right)f\left[b\right]\left[j\right]=f\left[j\right]\left[b\right]=min\left(f\right[a\left]\right[j],mp[a\left]\right[b\left]\right)$if(v[j])   f[b][j]=f[j][b]=min(f[a][j],mp[a][b])
理解的话=。=，读者自己尝试理解理解吧（就是只考虑 $f\left[当前点\right]\left[已访问的点\right]$f[当前点][已访问的点]，而先不考虑其子树）。
每次 $O\left(1\right)$O(1) 判断就可以了。

第二种做法

倍增。
每次询问，我们只需要用倍增，求出环上的最大边就好了。然后就没啥子了= =。

其实两种做法的区别仅仅在于离线和在线而已。（当然第一种好写的多，但第二种复杂度更优秀）

代码如下

#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100005
using namespace std;
struct node{
	int a, b, c, n;
	bool operator < (const node & A) const{
		return c < A.c;
	}
}e[N], d[N];
int g[105][105], f[105], h[105], vis[N], v[N], cnt, n, m;
void cr(int a, int b, int c){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
int find(int x){
	return x == f[x]? x: f[x] = find(f[x]);
}
void dfs(int a){
	int i, b, j, c;
	v[a] = 1;
	for(i = h[a]; i; i = d[i].n){
		b = d[i].b; c = d[i].c;
		if(!v[b]){
			v[b] = 1;
			for(j = 1; j <= n; j++) if(v[j]) g[b][j] = g[j][b] = max(g[a][j], c);
			dfs(b);
		}
	}
}
int main(){
	int i, j, T, ans, a, b, c, flag;
	scanf("%d", &T);
	while(T--){
		memset(v, 0, sizeof(v));
		memset(vis, 0, sizeof(vis));
		memset(h, 0, sizeof(h));
		memset(g, 0, sizeof(g));
		ans = cnt = flag = 0;
		scanf("%d%d", &n, &m);
		for(i = 1; i <= n; i++) f[i] = i;
		for(i = 1; i <= m; i++) scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
		sort(e + 1, e + i);
		for(i = 1; i <= m; i++){
			a = find(e[i].a); b = find(e[i].b); c = e[i].c;
			if(a != b){
				f[a] = b;
				cr(a, b, c);
				cr(b, a, c);
				ans += c;
				vis[i] = 1;
			}
		}
		dfs(1);
		for(i = 1; i <= m; i++){
			if(!vis[i]){
				a = e[i].a; b = e[i].b; c = e[i].c;
				if(c == g[a][b]) flag = 1;
			}
		}
		if(flag) printf("Not Unique!\n");
		else printf("%d\n", ans);
	}
	return 0;
}