uva 11695 Flight Planning

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

树dp

题意：给一个无根树，消掉一条边，新增一条边，求新的树的最长链，问怎么消边和加边，使得最长链的长度最小（HDU 3145一样的题目，不过注意输入，HDU是没有case数的）

假设选择一条边a–b断掉，使得树断裂为两个部分A,B，假设在A中选一个一个点rtA，和B中选一个点rtB，将两点；连接，得到一个新树，那么这个新树的最长链是多少呢？

最长链只有3个可能

  1. 完全来自于A部分，假设长度为lengthA
  2. 完全来自于B部分，长度为lengthB
  3. 来自于A,B部分，那么就一定经过rtA和rtB，另外一定是从rtA往A部分走出一条最长路t1，从rtB往B部分走出一条最长路t2。那么整个树的最长链就是max(lengthA , lengthB , t1+t2+1);

可以知道，无论怎么选择rtA，rtB都好，lengthA和lengthB都是不变的。但选择不同的rtA和rtB，则会影响t1和t2的值，那么怎么影响呢？

我们的目的是为了使最大值最小，那么就是令t1，t2尽量小，这里有一个结论，t1的最小值是[lengthA/2]上整，t2最小值[lengthB/2]上整，也就是说rtA是A部分的最长链的中点，rtB是B部分最长链的中点

证明：

对于A部分

  1. 先找出A部分的最长链，并且标记链上的点，染成红色，其他点是白色
  2. 一个显然的结论就是，如果选了红色的点做根，这个点刚好是链的中点的话，它能走出的最长路就是L/2；如果不是中点，那么它没有将最长链平分，最长链被分为2部分，长度为x，y，假设x < y，那么y肯定是超过链的一半的，且y也是那个根能走出的最长链
  3. 如果选的点不是红点而是白点为根，那么一定可以从根先走到红点，距离是t，然后走到了红点，一定有2条路可以走，如果2条路刚好是平分的，那么走过的路程是t+L/2，如果不平分，就跟2情况一样，可以选较长的那边继续走，距离是t+y

所以选白点，花费一定大于红点的，而选红点的情况里，选中点是最少的，所以就是选中点最少

所以我们要做的工作就很简单了

  1. 枚举原树中的每条边，删除它，得到A,B部分
  2. 在A部分求一次最长链并找到链的中点rtA
  3. 在B部分求一次最长链并找到链的中点rtB
  4. rtA和rtB相连，那么新树的最长链 = max(lengthA,lengthB,[lengthA/2] + [lengthB/2] + 1);
  5. 用现在的最长链去更新答案

优化：

可以先对原树求一次最长链，然后枚举删边的时候，只枚举最长链上的边，因为，如果不是断开最长链的边，那么得到的新树，其最长链肯定还是原树的最长链，是不可能更新答案的
枚举全部边时间是2500ms,枚举原树最长链上的边时间为750ms,在hdu排名第一，纪念一下
这题在网上应该是找不到题解的，找了很久找到了官方的，不过没有代码

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
148
149
150
151
152
153
#pragma comment(linker,"/STACK:10240000,10240000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
using namespace std;
#define N 2510
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pii pair<int,int>
#define mp make_pair

int dp[N][2],id[N][2];
int a,b,ra,rb,rc,rd,ANS;
int n,tot,head[N];
struct edge{
	int u,v,next;
}e[2*N];
int maxlink,root;
pii Link[N]; int length;
int LinkA[N],lengthA,rtA;
int LinkB[N],lengthB,rtB;

inline void add(int u,int v){
	e[tot].u = u; e[tot].v = v;
	e[tot].next = head[u]; head[u] = tot++;
}

void dfs(int u,int fa){
	dp[u][0] = dp[u][1] = 0;
	id[u][0] = id[u][1] = -1;
	for(int k = head[u]; k != -1; k = e[k].next){
		int v = e[k].v;
		if(v == fa || (u == a && v == b) || (u == b && v == a)) continue;
		dfs(v,u);
		if(dp[v][0] + 1 > dp[u][0]){
			dp[u][1] = dp[u][0]; id[u][1] = id[u][0];
			dp[u][0] = dp[v][0] + 1; id[u][0] = v;
		}
		else if(dp[v][0] + 1 > dp[u][1]){
			dp[u][1] = dp[v][0] + 1; id[u][1] = v;
		}
	}
	if(dp[u][0] + dp[u][1] > maxlink){
		maxlink = dp[u][0] + dp[u][1]; root = u;
	}
}

void Find(int u){
	while(true){
		if(id[u][0] == -1) break;
		Link[length++] = mp(u,id[u][0]);
		u = id[u][0];
	}
}

void Find_Link(){
	length = 0;
	if(id[root][0] != -1){
		Link[length++] = mp(root,id[root][0]);
		Find(id[root][0]);
	}
	if(id[root][1] != -1){
		Link[length++] = mp(root,id[root][1]);
		Find(id[root][1]);
	}
}

void path_1(int u,int f){
	if(u == -1) return ;
	path_1(id[u][0],f);
	if(!f) LinkA[lengthA++] = u;
	else LinkB[lengthB++] = u;
}

void path_2(int u,int f){
	u = id[u][1];
	while(u != -1){
		if(!f) LinkA[lengthA++] = u;
		else LinkB[lengthB++] = u;
		u = id[u][0];
	}
}

void Get_Link(int f){
	if(!f) lengthA = 0;
	else   lengthB = 0;
	path_1(root,f);
	path_2(root,f);
}

void solve(){
	ANS = INF;
	for(int i = 0; i < length; i++){ //枚举切断最长链上的边
		a = Link[i].first; b = Link[i].second;
		maxlink = root = -1;
		dfs(a,-1); //A树上求最长链
		Get_Link(0);
		maxlink = root = -1;
		dfs(b,-1); //B树上求最长链
		Get_Link(1);
		rtA = LinkA[lengthA/2]; 
		rtB = LinkB[lengthB/2];
		int t1 = lengthA / 2;
		int t2 = lengthB / 2;
		int Max;
		Max = max(lengthA-1,lengthB-1);
		Max = max(Max,t1+t2+1);
		if(Max < ANS){
			ANS = Max; 
			ra = a; rb = b; rc = rtA; rd = rtB; 
		}
	}
	printf("%d\n",ANS);
	printf("%d %d\n",ra,rb);
	printf("%d %d\n",rc,rd);
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
	//while(scanf("%d",&n)!=EOF){
		scanf("%d",&n);
		tot = 0; cl(head,-1);
		for(int i = 1; i < n; i++){
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v); add(v,u);
		}
		a = b = -1;
		dfs(1,-1);
		Find_Link();
		solve();
	}
	return 0;
}

/*
void Test(){
	puts("------------------");
	printf("a b : %d %d\n",a,b);
	printf("LinkA = %d\n",lengthA);
	for(int i = 0; i < lengthA; i++)
		printf("%d ",LinkA[i]);
	puts("");
	printf("LinkB = %d\n",lengthB);
	for(int i = 0; i < lengthB; i++)
		printf("%d ",LinkB[i]);
	puts("");
	puts("------------------");
}
*/