By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 分析：
  3. 3. 求次小生成树：

题目大意：

　　判断最小生成树是否唯一。

分析：

　　就是找他的次小生成树是否权值也等于最小生成树。

求次小生成树：

  • 用prime算法求最小生成树的同时，记录每个连通点的父节点，并用dp记录出生成树上u到v 路径上权值最大的边。
1
2
3
4
5
6
7
//用sta数组(栈)记录生成树连通的节点
//dp 求连通的树上u到v路径上权值最大的边
//pos是刚加入的点，mins是刚加入的边
for(int k = 0; k < top; k++){
	maxValue[sta[k]][pos] = maxValue[pos][sta[k]]
		= max(mins, maxValue[sta[k]][father[pos]]);
}

  • 枚举生成树外的边，边uv替换生成树u到v路径上权值最大的边。这里可以通过计算mp[i][j]与 maxValue[i][j差值，求出最小的来，如果是0，就说明MST和次小生成树一样。

  • 补： 用sta数组(栈)记录生成树连通的节点,通常可以通过top == n来判断是否是生成树.kruskal算法可以通过看祖先节点的ranks[祖先] == n来判断是否是生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;

int T, n, m, x, y, w;
int father[MAXN], lowcost[MAXN], maxValue[MAXN][MAXN], mp[MAXN][MAXN], sta[MAXN];
bool vis[MAXN];

void init()
{
	memset(vis, false, sizeof(vis));
	memset(maxValue, 0, sizeof(maxValue));
	memset(sta, 0, sizeof(sta));
	for(int i = 1; i <= n; i++){
		father[i] = 1;
		for(int j = 1; j <= n; j++)
			mp[i][j] = INF;
	}
}

void solve()
{
	//prime算法
	int ans = 0, pos;
	for(int i = 1; i <= n; i++){
		lowcost[i] = mp[1][i];
	}
	vis[1] = true;
	int top = 0;
	sta[top++] = 1; //开一个栈来记录连通的点
	for(int i = 1; i <= n; i++){
		pos = -1;
		int mins = 0x3f3f3f3f;
		for(int j = 1; j <= n; j++){
			if(!vis[j] && (pos == -1 || lowcost[j] < lowcost[pos])){
				pos = j;
				mins = lowcost[pos];
			}
		}
		if(pos == -1)
			break;
		ans += mins;
		vis[pos] = true;

		//dp 求连通的树上u到v路径上权值最大的边
		for(int k = 0; k < top; k++){
			maxValue[sta[k]][pos] = maxValue[pos][sta[k]]
				= max(mins, maxValue[sta[k]][father[pos]]);
		}

		sta[top++] = pos//记录连通的点;

		for(int j = 1; j <= n; j++){
			if(!vis[j] && lowcost[j] > mp[pos][j]){
				lowcost[j] = mp[pos][j];
				father[j] = pos;//记录将加入的结点的父节点，也就是记录生成树上每个点的父节点
			}
		}
	}

	//求最小生成树
	int mins = INF;
	for(int i = 1; i <= n; i++){
					//如果不是自己到自己的边，且不是生成树上的边
		for(int j = 1; j <= n; j++)if(i != j && mp[i][j] != INF && father[i] != j && father[j] != i){
			if(mins > mp[i][j] - maxValue[i][j])
				mins = mp[i][j] - maxValue[i][j];
		}
	}
	if(mins == 0)
		printf("Not Unique!\n");
	else
		printf("%d\n", ans);
}

int main()
{
    freopen("input.txt", "r", stdin);
    scanf("%d", &T);
	while(T--){
		scanf("%d%d", &n, &m);
		init();
		for(int i = 0; i < m; i++){
			scanf("%d%d%d", &x, &y, &w);
			if(mp[x][y] > w)//这里记得处理一下
				mp[x][y] = mp[y][x] = w;
		}
		solve();
		}

	return 0;
}
Contents
  1. 1. 题目大意：
  2. 2. 分析：
  3. 3. 求次小生成树：