Posts Tagged ‘树型动态规划’

POJ 2152 Fire

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

2010-??-??，阅读题目，分析，无果。
2010-03-07，从JBY问到这题的题解，原来在2006年冬令营，陈启峰论文中有这题的题解。
2010-03-08，POJ出毛病，在百练上提交，一次AC。

解题报告：详细参阅陈启峰论文《一张一弛，解题之道——“约制、放宽”方法在解题中的应用》中的解题报告（点击这里下载）。
我说说代码实现：
1. 计算每2点间距离；
2. 按照根-儿子方式列出所有点，并且可以直接根据这个序号迅速判断出点v是否在点u为根的子树中；
3. 按照2中序列的倒序分别计算每一个点u的f(u, v)；
4. 答案为f(1, v)，1 <= v <= n。
其实我实现得一点都不好，我很好奇POJ上面那位神牛的16ms是怎么实现的。

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

#include <stdio.h>
#include <string.h>
 
const int maxn = 1003, INF = 0x3FFFFFFF;
int n, w[maxn], d[maxn], edge[maxn][maxn], et[maxn], ew[maxn][maxn];
int dist[maxn][maxn], list[maxn], lp, pos[maxn][2], dp[maxn][maxn], best[maxn], answer;
 
int input() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &w[i]);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &d[i]);
	memset(et, 0, sizeof(et));
	for (int i = 1; i < n; ++i) {
		int u, v, p;
		scanf("%d%d%d", &u, &v, &p);
		edge[u][et[u]++] = v;
		edge[v][et[v]++] = u;
		ew[u][v] = ew[v][u] = p; 
	}
	return 0;
}
 
int min(int x, int y) {
	return x < y ? x : y;
}
 
int calc_dist() {
	int q[maxn], head, last;
	bool vis[maxn];
	for (int s = 1; s <= n; ++s) {
		memset(vis, 0, sizeof(vis));
		head = 0, last = 1;
		q[1] = s;
		vis[s] = 1;
		dist[s][s] = 0;
		while (head < last) {
			int u = q[++head];
			for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i])
				if (!vis[v]) {
					q[++last] = v;
					vis[v] = 1;
					dist[s][v] = dist[s][u] + ew[u][v];
				}
		}
	}
	return 0;
}
 
int calc_list(int u, int fu) {
	int k = 0;
	list[++lp] = u;
	pos[u][0] = lp;
	for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i])
		if (v != fu) {
			edge[u][k++] = v;
			calc_list(v, u);
		}
	pos[u][1] = lp;
	et[u] = k;
	return 0;
}
 
int work() {
	calc_dist();
	lp = 0;
	calc_list(1, 0);
	for (int i = n, u = list[n]; i > 0; u = list[--i]) {
		for (int j = 1, v = list[1]; j <= n; v = list[++j])
			if (dist[u][v] > d[u]) {
				dp[u][v] = INF;
			} else if (u == v || j < pos[u][0] || j > pos[u][1]) {
				dp[u][v] = u == v ? w[u] : 0;
				for (int k = 0, p = edge[u][0]; k < et[u]; p = edge[u][++k]) {
					dp[u][v] += min(best[p], dp[p][v]);
					dp[u][v] = min(dp[u][v], INF);
				}
			} else {
				dp[u][v] = 0;
				for (int k = 0, p = edge[u][0]; k < et[u]; p = edge[u][++k]) {
					dp[u][v] += j < pos[p][0] || j > pos[p][1] ? min(best[p], dp[p][v]) : dp[p][v];
					dp[u][v] = min(dp[u][v], INF);
				}
			}
		best[u] = INF;
		for (int j = pos[u][0], v = list[pos[u][0]]; j <= pos[u][1]; v = list[++j])
			best[u] = min(best[u], dp[u][v]);
	}
	answer = INF;
	for (int i = 1; i <= n; ++i)
		answer = min(answer, dp[1][i]);
	return 0;
}
 
int output() {
	printf("%d\n", answer);
	return 0;
}
 
int main() {
	int testCases;
	scanf("%d", &testCases);
	while (testCases--) {
		input();
		work();
		output();
	}
	return 0;
}