次小生成树原理+模板

原理:

  • 枚举每一条不在最小生成树上的边作为最小生成树上的边,那么形成了一个环,将环上的最长的路(除了枚举的这一条边)去掉,更新这颗次小生成树的权值和,
  • 最后与最小生成树的权值和比较.相同则说命存在.
  • 其实如果次小生成树存在.在最小生成树中肯定存在一条边与图中不在最小生成树的边的权值相同.
  • 通过枚举点来枚举每一条不在最小生成树上的边
  1. pre[maxn]:记录每个点的上一个点
  2. maxdist[maxn][maxn]:更新最小生成树中,2点之间的最大边.
  3. use[maxn][maxn]:标记边是否在最小生成树中.
  4. 最小生成树2点之间最大边更新原理: 图片
    `if (vis[j]) 
             maxdist[j][point] = maxdist[point][j] =max(maxdist[j][pre[point]],dist[point]);`

prim+例题POj 1679

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
#include <iostream>
#include <iostream>
#include <string.h>

using namespace std;
const int maxn = 1e3+5;
const int INF = 0x3f3f3f3f;

bool vis[maxn];
int dist[maxn];
int e[maxn][maxn];
int n,m;
int sum;
bool use[maxn][maxn];
int maxdist[maxn][maxn];
int pre[maxn];

int prim() {
	sum = 0;
	memset(vis,0,sizeof vis);
	memset(use,0,sizeof use);
	memset(maxdist,0,sizeof maxdist);
	vis[1] = 1; //点1加入到最小生成树中
	for (int i=2; i<=n; i++) {
		dist[i] = e[1][i];
		pre[i] = 1;
	}
	pre[1] = 0;

	for (int i=1; i<n; i++) {
		int minn = INF;
		int point = INF;
		for (int j=1; j<=n; j++) {
			if (!vis[j] && dist[j]<minn) {
				point = j;
				minn = dist[j];
			}
		}
		vis[point] = 1;
		sum += minn;
		use[point][pre[point]] = use[pre[point]][point] = 1; //标记在树的点

		for (int j=1; j<=n; j++) { //更新每个点到树的距离
			if (vis[j]) 
				maxdist[j][point] = maxdist[point][j] =max(maxdist[j][pre[point]],dist[point]);
			if (!vis[j] && e[point][j] < dist[j]) {
				dist[j] = e[point][j];
				pre[j] = point; //既然更新了路径,也更新该点指向的上一个点
			}
		}
	}
	return sum;
}
int superprim() {
	int ans = INF;
	for (int i=1; i<=n; i++) { //枚举所有的
		for (int j=i+1; j<=n; j++) {
			if (!use[i][j] && e[i][j]!=INF) 
				ans = min(sum+e[i][j]-maxdist[i][j],ans);
		}
	}
	return ans;
}

int main() {
//	freopen("a.txt","r",stdin);
	int times; cin >> times;
	while (times--) {
		cin >> n >> m;
		memset(e,0x3f,sizeof e);
		for (int i=1; i<=m; i++) {
			int u,v,w;
			cin >> u >> v >> w;
			e[u][v] = e[v][u] = min(e[u][v],w);
		}
		if(prim()==superprim())///判断次小生成树和最小生成树的结果是否一样
            printf("Not Unique!\n");
        else
            printf("%d\n",sum);
	}
	return 0;
}
算法
次小生成树

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！