Steven_MengのBlog

P3761 [TJOI2017]城市

注意到两个城市之间的最大交通费用就是树的直径。

考虑枚举删去哪一条边,假设删的是边$u,v$,那么我们发现直径可能有三种选择:

$1.$直径缩在蓝色子树里面。

$2.$直径缩在红色子树里面。

上面两种情况,我们都不能通过加边来缩短直径,是无法掌控的。


$3.$直径的一段在蓝色子树里面,另一端在红色子树里面,这时直径必定跨越边$u,v$

如图所示,黄色部分代表直径。

注意图中的$u,v$是你新增的边的端点。

于是问题转化为在蓝色子树和红色子树里面选两个点$p,q$,并且连边,使得蓝色子树里面的点到$p$的距离最大值+$u,v$边权+红色子树里面的点到$q$的距离的最大值最小。

不妨将这样的点称为树的中心,将树的中心和树上每一个点之间距离的最大值称为树的半径。

感性理解一下,树的中心一定在直径上面。

如何证明呢?

考虑把整棵树表示为直径上面连着一大堆子树的形式。

假设我们现在选择了某个子树里面的点$u$,设$v$是这个子树的根的父亲,考虑证明$v$是更优的选择。

把距离$u$最远的点记为$w$。

$1.w$不属于这个子树​:$dis(u,w)=dis(u,v)+dis(v,w)>dis(v,w)$,显然选择$v$最优。

$2.w$属于这个子树:

慢慢证明:

首先,树上距离$v$最远的点一定是$p$或$q$。

否则假设距离$v$最远的点是$r$,那么$p-v-r$或者$r-v-q$这条路径肯定比$p-v-q$长,$p-q$就不是直径了。

由于对称性,不妨设距离$v$最远的点是$p$。

我们有$dis(u,w)>dis(u,v)+dis(v,p)$

考虑设$u-w,u-v$路径的最上面一个交点为$O$。

注意到$dis(u,w)=dis(u,O)+dis(O,w)$。

且$dis(u,p)=dis(u,O)+dis(O,v)+dis(v,p)$。

那么$dis(u,p)<dis(u,w) \to dis(O,v)+dis(v,p)<dis(O,w)$。

而显然$dis(v,p)>dis(v,O)+dis(O,w)$(由于我们刚才的假设)

那么$dis(O,v)+dis(v,p)>dis(O,w)+dis(O,v) \times 2$。

和上面的式子矛盾。

所以$w$肯定不属于这个子树。

所以,我们找出蓝色部分和红色部分的子树,枚举直径上面每个点,计算这个点和直径两个端点的距离即可。

时间复杂度$O(n^2)$

代码:

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
#include <bits/stdc++.h>
#define MAXN 5005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct Edge{
int to,len;
};
vector<Edge>G[MAXN];
inline void AddEdge(int u,int v,int w){
G[u].push_back(Edge{v,w});
}
int n;
int fa[MAXN],d[MAXN];
int vis[MAXN];
queue<int>Q;
inline int bfs(int u,int father){
while (Q.size()) Q.pop();
memset(vis,0,sizeof(vis));
memset(fa,0,sizeof(fa));
memset(d,0,sizeof(d));
fa[u]=father,d[u]=0;
vis[u]=vis[father]=1;//等于是阻断到另一个子树的路
Q.push(u);
int ans=0;
while (Q.size()){
int u=Q.front();Q.pop();
vis[u]=true;
if (d[u]>d[ans]) ans=u;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i].to,w=G[u][i].len;
if (vis[v]) continue;
d[v]=d[u]+w;
fa[v]=u;//记录父亲,等于是记录直径
Q.push(v);
}
}
return ans;
}
inline int FindMid(int p,int q){//树的半径的长度,q为最深的点
int len=d[q];
int ans=0x7fffffff;
while (true){
ans=min(ans,max(d[q],len-d[q]));
q=fa[q];//慢慢爬上来
if (q==0) break;
}
return ans;
}
int U[MAXN],V[MAXN],W[MAXN];
int main(){
int n=read();
for (register int i=1;i<n;++i){
U[i]=read(),V[i]=read(),W[i]=read();
AddEdge(U[i],V[i],W[i]);
AddEdge(V[i],U[i],W[i]);
}
int ans=0x7fffffff;
for (register int i=1;i<n;++i){
int u=U[i],v=V[i];

int p1=bfs(u,v);int q1=bfs(p1,v);//直径的两个端点
int len1=d[q1];int ans1=FindMid(p1,q1);

int p2=bfs(v,u);int q2=bfs(p2,u);
int len2=d[q2];int ans2=FindMid(p2,q2);

ans=min(ans,max(max(len1,len2),ans1+W[i]+ans2));
}
printf("%d\n",ans);
}

总结:

在此题中我们大量使用反证法,通过构造新的直径和更长的长度来证明结论。

 评论