最小树形图专题

本文从WordPress迁移而来, 查看全部WordPress迁移文章

最小树型图这个内容其实有点鸡肋，用得不多，能找到的题目多时模板题，题目都是要求输出最小树形图的总权和，并没有要求输出最小树形图的具体形状，如果真要输出输出完整的最小树形图，应该要改掉整个代码实现，在这个方面没有深究

最小树形图模板——来自小HH

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
int Directed_MST(int root,int nv,int ne){
	int res = 0;
	while(true){
		cl(in,0x3f,sizeof(in));
		for(int i = 0; i < ne; i++){
			int u = e[i].u , v = e[i].v;
			if(u != v && e[i].w < in[v]){
				in[v] = e[i].w; pre[v] = u;
			}
		}
		for(int i = 0; i < nv; i++){
			if(i == root) continue;
			if(in[i] == INF) return -1;
		}

		in[root] = 0;
		cl(id,-1,sizeof(id));
		cl(vis,-1,sizeof(vis));
		int cntnode = 0;
		for(int i = 0; i < nv; i++){
			int v = i;
			res += in[i];
			while(vis[v] != i && id[v] == -1 && v != root){
				vis[v] = i; v = pre[v];
			}
			if(v != root && id[v] == -1){
				for(int u = pre[v]; u != v; u = pre[u]){
					id[u] = cntnode;
				}
				id[v] = cntnode++;
			}
		}
		if(cntnode == 0) break;
		for(int i = 0; i < nv; i++)
			if(id[i] == -1)
				id[i] = cntnode++;
		for(int i = 0; i < ne; i++){
			int temp = e[i].v;
			e[i].u = id[e[i].u];
			e[i].v = id[e[i].v];
			if(e[i].u != e[i].v)
				e[i].w -= in[temp];
		}
		nv = cntnode;
		root = id[root];
	}
	return res;
}

下面是几道题目，可以说都是模板题