Posts Tagged ‘最小树形图’

POJ 3164 Command Network

Posted in PKU OJ on 五月 13th, 2010 by 纳米 – Be the first to comment

上一篇说了，是五一做的。这题是五一开的，昨天看的，然后昨天实现的。中间那么多天干什么了呢？一是我病了，啥都没做（不过买了台D3000），二是去APIO了。这题十分郁闷的是，居然又调试了一个晚上。

解题报告：
这题是给出m个点在平面上的坐标，然后给出m组有序对(u_i, v_i)，表示添加从点u_i到点v_i的有向边，边权自然为两点间距离。求以点1为根的最小树形图。好了我承认我很懒，请看这个：

学了不少算法，终于第一次学会了以中国人的名字命名的算法，最小树形图的朱-刘算法。前几天看过书、ppt和网上相关的blog，在收缩环关键的那块总看得稀里糊涂。昨晚终于在威士忌的blog上看到了一幅最小树形图的构造流程图，登时大彻大悟。有时一张恰当好处的图表的确胜过万千文字解说。早上起来把它实现了，调试到现在，进一步把各种模糊的细节处理弄清楚了，也终于AC了POJ3164。呵呵

网上关于算法的描述有一些，我总结成bin3版。

有固定根的最小树形图求法O(VE)：

首先消除自环，显然自环不在最小树形图中。然后判定是否存在最小树形图，以根为起点DFS一遍即可。

之后进行以下步骤。

设cost为最小树形图总权值。
0.置cost=0。
1.求最短弧集合Ao （一条弧就是一条有向边）

除源点外，为所有其他节点Vi，找到一条以Vi为终点的边，把它加入到集合Ao中。

（加边的方法：所有点到Vi的边中权值最小的边即为该加入的边，记prev[vi]为该边的起点，mincost[vi]为该边的权值）

2.检查Ao中的边是否会形成有向圈，有则到步骤3，无则到步骤4。

（判断方法：利用prev数组，枚举为检查过的点作为搜索的起点，做类似DFS的操作）

3.将有向环缩成一个点。
假设环中的点有（Vk1，Vk2，… ，Vki）总共i个，用缩成的点叫Vk替代，则在压缩后的图中，其他所有不在环中点v到Vk的距离定义如下：
gh[v][Vk]=min { gh[v][Vkj]-mincost[Vkj] } (1<=j<=i)而Vk到v的距离为
gh[Vk][v]=min { gh[Vkj][v] } (1<=j<=i)
同时注意更新prev[v]的值，即if(prev[v]==Vkj) prev[v]=Vk
另外cost=cost+mincost[Vkj] (1<=j<=i)

到步骤1.

4.cost加上Ao的权值和即为最小树形图总权值。

如要输出最小树形图较烦，没实现过。

找环O(V)，收缩O(E)，总复杂度O(VE)。

那幅对我有莫大帮助的流程图如下，

最小树形图

对于不固定根的最小树形图，wy教主有一巧妙方法。摘录如下：

新加一个点，和每个点连权相同的边，这个权大于原图所有边权的和，这样这个图固定跟的最小树形图和原图不固定跟的最小树形图就是对应的了。

转载自：最小树形图_bin3学艺录（恶心的百度不让外链，我把图片搞到SkyDrive上了）

说一下我对时间复杂度的理解，我认为上面对时间复杂度的分析比较笼统，应该是这样的：找环是O(|V|)的，消环是O(|E|)的，但是由于这两个操作是并列的，所以一次操作的时间复杂度是O(|V|+|E|)；每一次消环，最坏情况只减少1个点，所以一共可能有O(|V|)次操作，所以总时间复杂度应为O(|V|^2 + |V||E|)，不严格情况下写作O(|V||E|)也是可以的。

邻接矩阵实现，写得不好，常数比较大：

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

#include <stdio.h>
#include <string.h>
#include <math.h>
 
const int maxn = 103;
int n, pv[maxn]; // pv -> pre v
bool ee[maxn][maxn], il[maxn]; // ee -> edge exist, il -> in loop
double ew[maxn][maxn], pw[maxn], answer; // ew -> edge weight, pw -> the weight of pre v
 
bool input() {
	int m, u, v;
	double pos[maxn][2];
	if (scanf("%d%d", &n, &m) == EOF)
		return false;
	memset(ee, 0, sizeof(ee));
	for (int i = 1; i <= n; ++i)
		scanf("%lf%lf", &pos[i][0], &pos[i][1]);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		if (u != v) {
			ee[u][v] = true;
			ew[u][v] = sqrt((pos[u][0]-pos[v][0])*(pos[u][0]-pos[v][0]) + (pos[u][1]-pos[v][1])*(pos[u][1]-pos[v][1]));
		}
	}
	return true;
}
 
bool check_connect() {
	bool vis[maxn], res = true;
	int q[maxn] = {1}, head = -1, last = 0;
	memset(vis, 0, sizeof(vis));
	while (head < last) {
		int u = q[++head];
		for (int v = 2; v <= n; ++v)
			if (ee[u][v] && !vis[v]) {
				vis[v] = true;
				q[++last] = v;
			}
	}
	for (int v = 2; v <= n && res; ++v)
		res = res & vis[v];
	return res;
}
 
void calc_p() {
	for (int v = 0; v <= n; ++v)
		pv[v] = 0, pw[v] = 1e15;
	for (int u = 1; u <= n; ++u)
		for (int v = 2; v <= n; ++v)
			if (ee[u][v] && ew[u][v] < pw[v]) {
				pv[v] = u;
				pw[v] = ew[u][v];
			}
}
 
bool check_loop() {
	int vis[maxn];
	memset(vis, 0, sizeof(vis));
	memset(il, 0, sizeof(il));
	vis[0] = vis[1] = 1;
	for (int i = 2; i <= n; ++i)
		if (!vis[i]) {
			int v = i;
			do {
				vis[v] = i;
				v = pv[v];
			} while (!vis[v]);
			if (vis[v] == i) {
				int v0 = v;
				do {
					il[v] = true;
					v = pv[v];
				} while (v != v0);
				return true;
			}
		}
	return false;
}
 
double remove_loop() {
	int nv = 0; // nv -> new_v
	double res = 0;
	for (int v = 2; v <= n; ++v)
		if (il[v]) {
			res += pw[v];
			nv = nv ? nv : v;
		}
	for (int u = 1; u <= n; ++u)
		for (int v = 1; v <= n; ++v)
			if (ee[u][v]) {
				if (il[u] && il[v]) {
					ee[u][v] = false;
				} else if (il[v]) {
					if (!ee[u][nv]) {
						ee[u][nv] = true;
						ew[u][nv] = 1e15;
					}
					ew[u][nv] = ew[u][v]-pw[v] < ew[u][nv] ? ew[u][v]-pw[v] : ew[u][nv];
					ee[u][v] = v == nv;
				} else if (il[u]) {
					if (!ee[nv][v]) {
						ee[nv][v] = true;
						ew[nv][v] = 1e15;
					}
					ew[nv][v] = ew[u][v] < ew[nv][v] ? ew[u][v] : ew[nv][v];
					ee[u][v] = u == nv;
				}
			}
	return res;
}
 
double sum_pre() {
	double res = 0;
	for (int v = 2; v <= n; ++v)
		if (pv[v])
			res += pw[v];
	return res;
}
 
double work() {
	if (!check_connect())
		return -1;
	double res = 0;
	calc_p();
	while (check_loop()) {
		res += remove_loop();
		calc_p();
	}
	res += sum_pre();
	return res;
}
 
int output() {
	if (answer > 0)
		printf("%.2f\n", answer);
	else
		printf("poor snoopy\n");
	return 0;
}
 
int main() {
	while (input()) {
		answer = work();
		output();
	}
	return 0;
}