树形练习及题解

字数统计: 4.7k字   |   阅读时长: 24分

已经AK了的就进来看看吧

黑暗爆炸4390 Max Flow

题意： 给定一棵有N个点的树，所有节点的权值都为0。有K次操作，每次指定两个点s,t，将s到t路径上所有点的权值都加一。请输出K次操作完毕后权值最大的那个点的权值。

树上点的差分 
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int _T, n, m;
int maxx;
int lca[maxn << 1];
int ans[maxn];
int vis[maxn];
int pre[maxn];

int cnt, head[maxn];
struct edge { int to, next; } e[maxn << 1];
void add (int u, int v) {
	e[++cnt] = {v, head[u]}; head[u] = cnt;
	e[++cnt] = {u, head[v]}; head[v] = cnt;
}

int tot, firs[maxn];
struct quer { int to, next; } q[maxn << 1];
void insert (int u, int v) {
	q[++tot] = {v, firs[u]}; firs[u] = tot;
	q[++tot] = {u, firs[v]}; firs[v] = tot;
}

int s[maxn];
int find (int x) { return s[x] == x ? x : s[x] = find(s[x]); }

void init () { 
	cnt = tot =  0;
	memset(vis,  0, sizeof vis );
	memset(head, 0, sizeof head);
	memset(firs, 0, sizeof firs);
	for (int i = 1; i <= n; ++i) s[i] = i; 
}

void Tarjan (int u, int fa) {
	pre[u] = fa;
	for (int i = head[u]; i; i = e[i].next) {
		if (e[i].to == fa) continue;
		Tarjan(e[i].to, u);
		s[e[i].to] = u;
	}
	for (int i = firs[u]; i; i = q[i].next) {
		if (!vis[q[i].to]) continue;
		lca[(i + 1) / 2] = find(q[i].to);
	}
	vis[u] = 1;
}

int DFS (int u) {
	int res = ans[u];
	for (int i = head[u]; i; i = e[i].next) {
		if (e[i].to == pre[u]) continue;
		res += DFS(e[i].to);
	}
	maxx = max(maxx, res);
	return res;
}

int main () {
	scanf("%d%d", &n, &m);
	init();
	for (int i = 1; i < n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y);
	}
	for (int i = 1; i <= m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		insert(x, y);
	}
	Tarjan(1, 0);
	for (int i = 1; i <= tot; i += 2) {
		ans[q[i].to]++, ans[q[i + 1].to]++, ans[lca[(i + 1) / 2]]--, ans[pre[lca[(i + 1) / 2]]]--;
	}
	DFS(1);
	printf("%d\n", maxx);
	return 0;
}

POJ3417 Network

题意： nn个节点，n−1n-1条旧边连接所有的点，还有m条新的边。问，删一条旧边和新边，将这些点分成两个部分，一共有多少种方案。

题解： 题目保证n−1n-1条旧边连接所有的点，也就是说但看旧边部分，就是一棵树；从这些边中任意删除一条，一定能将这棵树分成两部分。再看m条新边。

假设一条新边建在了u点和v点之间：

  • 如果不删除这条新边，单单删除u和v之间的旧边，是不足以将树分成连个部分的。必须要删除这条新边，删除u和v之间的旧边才能将树分成两个部分。
  • 除了u和v之间的所有旧边，因为没有新边的干扰，删除任意一条都能将树分成两部分。

假设右两条新边建在了u和v点之间：

  • 即使删除了一条新边，也会变成上一种情况，删除u和v之间的旧边不能将树分成两部分
  • 除了u和v之间的所有旧边，因为没有新边的干扰，删除任意一条都能将树分成两部分。

变式： 将原有的n-1条边，建成一棵树。所有边权为0。之后m条新边，看作是m次操作，u和v之间的新边，就看作是将u到v之间的所有边的权值都加上1。如此一来：

  • 某处u和v之间的边权为0。说明此处只有一条旧边，删除即可将树分成两个部分。另外还可以任意删除m条边。【题目要求删除一条旧边和一条新边】
  • 某处u和v之间的边权为1。说明此处右一条旧边和一条新边，需要同时将两条边都删除，才可将树分成两部分。
  • 某处u和v之间的边权大于1。说明此处不止一条新边，怎么删除都无济于事；。
树上边权的维护——树上边的差分。 
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
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 7;

int n, m;
int res;
int vis[maxn];
int ans[maxn];
int pre[maxn];

int s[maxn];
int find (int x) { return s[x] == x ? x : s[x] = find(s[x]); }

int cnt, head[maxn];
struct edge { int to, next; } e[maxn << 1];
void add (int u, int v) {
	e[++cnt].to = v, e[cnt].next = head[u], head[u] = cnt;
	e[++cnt].to = u, e[cnt].next = head[v], head[v] = cnt;
}

int tot, firs[maxn];
struct ques { int to, next; } q[maxn << 1];
void ins (int u, int v) {
	q[++tot].to = v, q[tot].next = firs[u], firs[u] = tot;
	q[++tot].to = u, q[tot].next = firs[v], firs[v] = tot;
}

void Tarjan (int u, int fa) {
	pre[u] = fa;
	for (int i = head[u]; i; i = e[i].next) {
		if (e[i].to != fa) Tarjan(e[i].to, u);
	}
	for (int i = firs[u]; i; i = q[i].next) {
		int v = q[i].to;
		if (!vis[v]) continue;
		ans[u]++, ans[v]++;
		ans[find(v)] -= 2;
	}
	vis[u] = 1;
	s[u] = fa;
}

void DFS (int u, int fa) {
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].to;
		if (v == fa) continue;
		DFS(v, u);
		ans[u] += ans[v];
	}
//	cout << u << " -> " << ans[u] << endl;
}

void run () {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) s[i] = i;
	for (int i = 1; i <  n; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d",&u, &v);
		ins(u, v);
	}
	Tarjan(1, 0); DFS(1, 0);
	for (int i = 2; i <= n; ++i) {
		if (ans[i] == 0) res += m;
		if (ans[i] == 1) res ++;
	}
	printf("%d\n", res);
}

int main () {
	run();
	return 0;	
}

POJ3107 Godfather

求树的重心 
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
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 5e4 + 10;

int n;
int sz[maxn];
int dp[maxn];

int cnt, head[maxn];
struct edge { 
	int to, next;
	edge () {}
	edge (int to, int next) : to(to), next(next) {}
} e[maxn << 1];

void add (int u, int v) {
	e[++cnt] = edge(v, head[u]); head[u] = cnt;
	e[++cnt] = edge(u, head[v]); head[v] = cnt;
}

void DFS (int u, int fa) {
	sz[u] = 1;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].to;
		if (v == fa) continue;
		DFS(v, u);
		sz[u] += sz[v];
		dp[u] = max(dp[u], sz[v]);
	}
	dp[u] = max(dp[u], n - sz[u]);
}

int main () {
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	DFS(1, -1);
	for (int i = 1; i <= n; ++i) {
		if (dp[i] <= n / 2) printf("%d ", i);
	}
	return 0;
}

HDU2196 Computer

题意： 一棵有根树，求所有节点在树中的最大距离。

树形DP 
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;

int n;
int dp[maxn][3];

int cnt, head[maxn];
struct edge { int v, w, next; } e[maxn << 1];
void add (int u, int v, int w) {
	e[++cnt] = {v, w, head[u]}; head[u] = cnt;
//	e[++cnt] = {u, w, head[v]}; head[v] = cnt;
}

void dfs (int u) {
	int fir = 0, sec = 0;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		dfs(v);
		int c = dp[v][0] + w;
		if (c > fir) sec = fir, fir = c;
		else if (c > sec) sec = c;
	}
	dp[u][0] = fir;
	dp[u][1] = sec;
}

void DFS (int u) {
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		if (dp[v][0] + w == dp[u][0])
			dp[v][2] = max(dp[u][1], dp[u][2]) + w;
		else 
			dp[v][2] = max(dp[u][0], dp[u][2]) + w;
		DFS(v);
	}
}

void run () {
	cnt = 0;
	memset(dp, 0, sizeof dp);
	memset(head, 0, sizeof head);
	for (int i = 2, u, w; i <= n; ++i) {
		scanf("%d%d", &u, &w);
		add(u, i, w);
	}
	dfs(1);
	DFS(1);
	for (int i = 1; i <= n; ++i) {
		printf("%d\n", max(dp[i][0], dp[i][2]));
	}
}

int main () {
	while (~scanf("%d", &n)) run();
	return 0;
}

POJ3140 Contestants Division

题意： 一棵带权树，删除某条边，求两棵子树的最小权值差。

题解： 定义dp[i]表示以i为根节点的子树的权值和。如果u是v的父节点，则有dp[u] = ∑dp[v]\sum{dp[v]}。如果切断u和v之间的边，权值差则为sum - 2 * dp[v]

树形DP 
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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define fab(a) (a) > 0 ? (a) : 0-(a)
typedef long long ll;
const int maxn = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m, cas;
ll ans, sum;
ll dp[maxn];

int cnt, head[maxn];
struct edge {
	int v, next;
	edge () {}
	edge (int v, int next) : v(v), next(next) {}
} e[maxn << 1];
void add (int u, int v) {
	e[++cnt] = edge(v, head[u]); head[u] = cnt;
	e[++cnt] = edge(u, head[v]); head[v] = cnt;
}

void DFS (int u, int fa) {
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (v == fa) continue;
		DFS(v, u);
		dp[u] += dp[v];
	}
	ans = min(ans, fab(sum - dp[u] - dp[u]));
}

void run () {
	ans = INF;
	cnt = sum = 0;
	memset(dp, 0, sizeof dp);
	memset(head, 0, sizeof head);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", dp + i);
		sum += dp[i];
	}
	for (int i = 1; i <= m; ++i) {
		int u, v; scanf("%d%d", &u, &v);
		add(u, v);
	}
	DFS(1, 0);
	printf("Case %d: %lld\n", ++cas, ans);
}

int main () {
	while (~scanf("%d%d", &n, &m) && (n + m)) run();
	return 0;
}

HDU1520 Anniversary party

题意： 公司宴会，员工之间存在直接的上下级关系，如果两人同时出席宴会会很尴尬，所以直接不允许这样的上下级同时出席。求宴会上能邀请的最大人数。

题解： 员工和直属上司不能同时出席。这题目乍一看就好像二分图匹配。啥是二分图匹配？不是今天的重点，自行百度。 直白点问，树形DP怎么做？

定义dp[i][0]表示不选择员工i能获得的最大人数。
定义dp[i][1]表示选择员工i能获得的最大人数。

那其实状态转移就很明了了【比如u是v的直属上司】

dp[u][0] += max(dp[v][1], dp[son][0]);虽然我不让u出席宴会，但不代表v一定要出席宴会。比较一下v出席和不出席能获得的最大人数，取其中较大值即可。
dp[u][1] += dp[v][0];这个就比较明确了，u想出席，v必须不能在场

树形DP 
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e3 + 10;

int _T, n;
int u, v, rt;
int a[maxn];
int dp[maxn][2];
int deg[maxn];

int cnt, head[maxn];
struct edge { int to, next; } e[maxn];
void add (int u, int v) { e[++cnt] = {v, head[u]}; head[u] = cnt; }

void init () {
	cnt = 0;
	memset(dp, 0, sizeof dp);
	memset(deg, 0, sizeof deg);
	memset(head, 0, sizeof head);
}

void dfs (int u) {
	dp[u][1] = a[u];
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].to;
		dfs(v);
		dp[u][0] += max(dp[v][0], dp[v][1]);
		dp[u][1] += dp[v][0];
	}
}

void run () {
	init();
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	while (~scanf("%d%d", &v, &u) && (u + v)) {
		deg[v]++, add(u, v);
	}
	for (int i = 1; i <= n; ++i) {
		if (deg[i] == 0) rt = i;
		
	}
	dfs(rt);
	printf("%d\n", max(dp[rt][0], dp[rt][1]));
}

int main () {
	while (~scanf("%d", &n)) run();
	return 0;
}

HDU3586 Information Disturbing

题意： 一棵有边权的树，要求删除一些边，使得根节点1和所有的叶子节点断开联系。要求是：

  • 删除的边的权值和必须小于m
  • 删除的边权的最大值尽可能小

题解： 两个条件看似是不能统一的，总和必须小于m，但是最大权值又要尽可能小。

举个栗子，如果DFS过程中追求权值和最小，那么将会得到答案6，但这个却不是最小的最大权。

对于这种，就应该去枚举最大权，然后DFS验证是否正确。当然，应该二分枚举。

树形DP + 二分 
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1100;

int n, m;
int dp[maxn];

int cnt, head[maxn];
struct edge { int v, w, next; } e[maxn << 1];
void add (int u, int v, int w) {
	e[++cnt] = {v, w, head[u]}; head[u] = cnt;
	e[++cnt] = {u, w, head[v]}; head[v] = cnt;
}

int DFS (int u, int fa, int lim) {
	dp[u] = 0;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		if (v == fa) continue;
		int c = (w > lim ? m + 1 : w);
		dp[u] += min(DFS(v, u, lim), c);
	}
	return dp[u] ? dp[u] : m + 1;
}

void run () {
	cnt = 0;
	memset(head, 0, sizeof head);
	for (int i = 1, u, v, w; i < n; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
	}
	int ans = -1;
	int l = 0, r = m;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (DFS(1, 0, mid) <= m) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", ans);
} 

int main () {
	while (~scanf("%d%d", &n, &m) && (n + m)) run();
	return 0;
}

POJ3162 Walking Race

题意： 一棵n个节点、有边权的树。第ii天则从点ii出发，记录下能跑到的最远距离。求一个最大的连续天数，使得其中的最大距离 - 最小距离 < m

题解： 树形DP求解每个点在树上的最远距离，然后线段树维护区间最大值与最小值。

树形DP + 线段树 
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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 1e6 + 10;

#define lrt rt << 1
#define rrt rt << 1 | 1

int n, m, ans;
int dp[maxn][3];

int cnt, head[maxn];
struct edge { 
	int v, w, next; 
	edge () {}
	edge (int v, int w, int next) : v(v), w(w), next(next) {}
} e[maxn << 1];
void add (int u, int v, int w) {
	e[++cnt] = edge(v, w, head[u]); head[u] = cnt;
	e[++cnt] = edge(u, w, head[v]); head[v] = cnt;
}

void dfs (int u, int fa) {
	int fir = 0, sec = 0;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		if (v == fa) continue;
		dfs(v, u);
		
		int c = dp[v][0] + w;
		if (c > fir) sec = fir, fir = c;
		else if (c > sec) sec = c;
	}
	dp[u][0] = fir;
	dp[u][1] = sec;
}

void DFS (int u, int fa) {
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		if (v == fa) continue;
		if (dp[u][0] == dp[v][0] + w) dp[v][2] = max(dp[u][1], dp[u][2]) + w;
		else dp[v][2] = max(dp[u][0], dp[u][2]) + w;
		
		DFS(v, u);
	}
}

struct node { 
	int l, r, max, min;
	int mid () { return l + r >> 1; }
} T[maxn << 2];

void build (int l, int r, int rt) {
	T[rt].l = l, T[rt].r = r;
	if (l == r) return (void)(T[rt].max = T[rt].min = max(dp[l][0], dp[l][2]));
	
	int mid = T[rt].mid();
	build(l, mid, lrt);
	build(mid + 1, r, rrt);
	
	T[rt].max = max(T[lrt].max, T[rrt].max);
	T[rt].min = min(T[lrt].min, T[rrt].min);
}

int max (int l, int r, int rt) {
	if (T[rt].l >= l && T[rt].r <= r) return T[rt].max;
	
	int mid = T[rt].mid();
	int maxx = 0;
	if (l <= mid) maxx = max(maxx, max(l, r, lrt));
	if (r >  mid) maxx = max(maxx, max(l, r, rrt));
	return maxx;
}

int min (int l, int r, int rt) {
	if (T[rt].l >= l && T[rt].r <= r) return T[rt].min;
	
	int mid = T[rt].mid();
	int minn = maxn;
	if (l <= mid) minn = min(minn, min(l, r, lrt));
	if (r >  mid) minn = min(minn, min(l, r, rrt));
	return minn;
}

void run () {
	ans = 1, cnt = 0;
	memset(dp, 0, sizeof dp);
	memset(head, 0, sizeof head);
	
	for (int v = 2, u, w; v <= n; ++v) {
		scanf("%d%d", &u, &w);
		add(u, v, w);
	}
	dfs(1, 0); DFS(1, 0);
	build(1, n, 1);
	int i = 1, j = 2;
	while (i <= j && j <= n) {
		int maxx = max(i, j, 1);
		int minn = min(i, j, 1);
		if (maxx - minn <= m) ans = max(ans, j - i + 1), ++j;
		else ++i;
		if (n - i < ans) break;
	}
	printf("%d\n", ans);
}

int main () {
	while (~scanf("%d%d", &n, &m)) run();
	return 0;
}

HDU4126 Genghis Khan the Conqueror

题意： 给定一个带权无向图G，n个点m条边，每条边都有一个权值w。题目保证两个点之间最多只有一条边。接下来有Q次边权的改变，且改变后的权值之后一定比原来的更大。求每次改变边权之后的所有最小生成树的平均值（边权的改变前后不影响。

题解：

  • 构造最小生成树： 在没有任何边权改变之前，求出最原始的最小生成树，记录这棵树的权值和ans。
  • 边权替换： 再次强调，每次边权的改变，是独立操作、前后互补影响的。明确之后再对改变的边权进行分类讨论：
    • 边在树上： 这次改变的边在最原始的最小生成树上，并且题目保证改变的边权一定比原来的大，所以一定会影响最小生成树的结果。办法是在原始的最小生成树上，断开这条改变的边，从分开的两棵树，找到一条连接两棵树的最小边。则新的生成树的权值和 = ans - 改变的边（原来的值） + 连接两棵树的最小边
    • 边不在树上： 如果改变的边不在原始的最小生成树上，那其实是不会影响结果的，改变后的最小生成树还是原来的生成树，那么权值和 = ans
  • 连接两棵子树的最小边： 既然我们决定将最小生成树上那条改变的边断开，那么这棵树就会分成两棵子树，但是要如何找到连接两棵子树的最小边？
    • 树形DP： 定义状态dp[u][v]表示点u在的这棵子树到点v在的这颗子树的最小边权。（树形DP这块太难解释了，看代码吧）
最小生成树 + 树形DP 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10;
const int inf = 0x3f3f3f3f;
typedef long long ll;

int n, m, Q, ans;
int u, v, w;
int pre[N];
int G[N][N];
int dp[N][N];
int d[N], vis[N];
vector<int> E[N];
struct edge{
	int u, v, w;
	bool operator<(const edge &a)const{return a.w < w;}
};

void prim(){
	priority_queue<edge> que;
	for(int i = 0; i < n; i++)	vis[i] = pre[i] = 0, d[i] = G[0][i], E[i].clear(), que.push({0, i, d[i]});
	ans = 0, vis[0] = 1, pre[0] = -1, d[0] = inf;
	while(!que.empty()){
		edge e = que.top(); que.pop();
		if(vis[e.v])	continue;
		ans += d[e.v];
		vis[e.v] = 1;
		pre[e.v] = e.u;
		E[e.u].push_back(e.v);	E[e.v].push_back(e.u);
		for(int i = 0; i < n; i++)	if(!vis[i] && d[i] > G[e.v][i])	d[i] = G[e.v][i], que.push({e.v, i, d[i]});
	}
}

int dfs(int u, int fa, int root){
	int res = inf;
	for(int i = 0; i < E[u].size(); i++){
		int v = E[u][i];
		if(v == fa)	continue;
		int tem = dfs(v, u, root);
		res = min(res, tem);
		dp[u][v] = dp[v][u] = min(dp[u][v], tem);
	}
	if(root != fa)	res = min(res, G[root][u]);
	return res;
}

int main(){
	while(~scanf("%d%d", &n, &m) && n && m){
		for(int i = 0; i < n; i++)	for(int j = 0; j < n; j++)	G[i][j] = dp[i][j] =  inf;
		for(int i = 0; i < m; i++){
			scanf("%d%d%d", &u, &v, &w);
			G[u][v] = G[v][u] = w;
		} 
		prim();
		for(int i = 0; i < n; i++)	dfs(i, -1, i);
		ll sum = 0;
		scanf("%d", &Q);
		for(int i = 1; i <= Q; i++){
			scanf("%d%d%d", &u, &v, &w);
			if(pre[u] != v && pre[v] != u)	sum += ans;
			else	sum += (ans - G[u][v] + min(w, dp[u][v]));
		}
		printf("%.4lf\n", 1.0 * sum / Q);
	}
	return 0;
}
文章目录
  1. 黑暗爆炸4390 Max Flow
  2. POJ3417 Network
  3. POJ3107 Godfather
  4. HDU2196 Computer
  5. POJ3140 Contestants Division
  6. HDU1520 Anniversary party
  7. HDU3586 Information Disturbing
  8. POJ3162 Walking Race
  9. HDU4126 Genghis Khan the Conqueror
|