很麻烦的一道基环外向树的题。

题目

3242: [Noi2013]快餐店

Time Limit: 20 Sec Memory Limit: 512 MB

Description

小T打算在城市C开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小T希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市C的\(N\)个建筑中,这\(N\)个建筑通过恰好\(N\)条双向道路连接起来,不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小T的快餐店可以开设在任一建筑中,也可以开设在任意一条道路的某个位置上(该位置与道路两端的建筑的距离不一定是整数)。 现给定城市C的地图(道路分布及其长度),请找出最佳的快餐店选址,输出其与最远的顾客之间的距离。

Input

第一行包含一个整数\(N\),表示城市\(C\)中的建筑和道路数目。 接下来\(N\)行,每行\(3\)个整数,\(A_i\)\(B_i\)\(L_i\)\(1≤i≤N\)\(L_i>0\)),表示一条道路连接了建筑\(A_i\)\(B_i\),其长度为\(L_i\)

Output

仅包含一个实数,四舍五入保留恰好一位小数,表示最佳快餐店选址距离最远用户的距离。 注意:你的结果必须恰好有一位小数,小数位数不正确不得分。 ## 数据范围 对于 \(10\%\)的数据,\(N<=80,L_i=1\); 对于 \(30\%\)的数据,\(N<=600,L_i<=100\); 对于 \(60\%\) 的数据,\(N<=2000,L_i<=10^9\); 对于 \(100\%\) 的数据,\(N<=10^5,L_i<=10^9\) # 解题报告 首先这是一颗环套树,这类题的套路貌似是把外向树和基环讨论; 1. 首先考虑树上的情况,这就很简单,就是求树的直径,然后取直径的终点,到直径两端的距离就是答案,这是显然好证的,所以在每棵外向树上都要跑一遍,复杂度是\(O(n)\)的,也就是构成答案的链在一棵外向树上的情况; 2. 考虑如果构成答案的链经过基环,我们需要证明这样一个结论:最终答案中一定有一条边是不经过的!这样想:

  • 当前找到一对最远点,这两点间的最短路一定不经过基环上一边;
  • 将这条边加入答案,会使当前最远点变得更远,从而答案变劣;如果使其他两对点变为最远点,这对点必然不如原答案优;
  • 所以得到结论,答案中一定有一条边不经过!

所以我们在基环上,每次删除一个点,求最远点.有一点可以确定的是,每棵外向树肯定会选择深度最大的点,两颗外向树之间的最远点可以表示为\(sum_j+dep_j+dep_i-sum_i\),其中,\(dep\)为外向树的最大深度,\(sum\)是基环上的前缀距离。可以维护\(sum+dep\)的最大值和\(sum-dep\)的最大值,每次求和,但是两个位置不能相同,所以需要同时维护次大值,判断+更新. 具体做法是在基环上枚举删除的边\(e_{i,j}\)使用完后,令\(sum_j=circlelength+sum_j\),也就是只能通过绕一圈到达\(j\)了. 还有一种做法是用单调队列,因为可以证明,\(max(sum_j+dep_j+dep_i-sum_i)\)中,\(i < j\),但因为我是调试的时候才发现的, 就愚蠢的又长又慢大线段树搞了。 # 代码

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
154
155
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N=100005;
const long long inf=10000000000000000LL;
char *cp=(char *)malloc(6000000);
struct E {
int next,to,v;
E(int next=0,int to=0,int v=0)
:next(next),to(to),v(v){}
} e[N<<1];
struct one {
long long mx[N<<2],se[N<<2];
int mxp[N<<2],sep[N<<2];
inline void init(int n){
for (int i=1;i<=n<<2;i++)
mx[i]=se[i]=-inf;
}
inline void up(int x) {
if (mx[x<<1]>=mx[x<<1|1]) {
mx[x]=mx[x<<1],mxp[x]=mxp[x<<1];
se[x]=mx[x<<1|1],sep[x]=mxp[x<<1|1];
}else {
mx[x]=mx[x<<1|1],mxp[x]=mxp[x<<1|1];
se[x]=mx[x<<1],sep[x]=mxp[x<<1];
}
if (se[x<<1]>se[x])
se[x]=se[x<<1],sep[x]=sep[x<<1];
if (se[x<<1|1]>se[x])
se[x]=se[x<<1|1],sep[x]=sep[x<<1|1];
}
void build(int x,int l,int r,long long *a,long long *b,int type) {
if (l==r) {
if (type==1) mx[x]=a[l]+b[l];
else mx[x]=a[l]-b[l];
mxp[x]=l;
}else {
int mid=(l+r)>>1;
build(x<<1,l,mid,a,b,type);
build(x<<1|1,mid+1,r,a,b,type);
up(x);
}
}
void insert(int x,int l,int r,int pur,long long val) {
if (l==r) {
mx[x]=val,mxp[x]=l;
}else {
int mid=(l+r)>>1;
if (pur<=mid)
insert(x<<1,l,mid,pur,val);
else
insert(x<<1|1,mid+1,r,pur,val);
up(x);
}
}
} plu,cha;
int n,head[N],tot=1,f[N],fp[N];
int cn,ban[N<<1],mxw,cir[N];
long long dp[N],mxdp,tree[N],r[N],sum[N],ans=-inf,cl;
bool vis[N];
inline void in(int &x) {
for (;*cp<'0'||*cp>'9';cp++);
for (x=0;*cp>='0'&&*cp<='9';cp++)
x=x*10+*cp-48;
}
inline void add(int x,int y,int v) {
e[++tot]=E(head[x],y,v),head[x]=tot;
}
inline void BAN(int x) {
ban[x]=ban[x^1]=1;
}
bool dfs(int x,int fa) {
int y; vis[x]=1;
for (int i=head[x];i;i=e[i].next) {
y=e[i].to;
if (y==fa) continue;
if (vis[y]) {
f[y]=x,cir[1]=y,fp[y]=i;
return 1;
}
f[y]=x,fp[y]=i;
if (dfs(y,x)) return 1;
}
return 0;
}
void DFS(int x,int fa) {
if (dp[x]>mxdp)
mxdp=dp[x],mxw=x;
int y;
for (int i=head[x];i;i=e[i].next) {
y=e[i].to;
if (y==fa||ban[i]) continue;
dp[y]=dp[x]+e[i].v;
DFS(y,x);
}
}
inline void findmx(int x) {
dp[cir[x]]=0;
DFS(cir[x],0),tree[x]=mxdp;
mxdp=-1,dp[mxw]=0;
DFS(mxw,0);
ans=max(ans,mxdp);
}
void circle() {
dfs(1,0);
int x=cir[1]; cn=0,r[1]=0;
for (;f[x]!=cir[1];x=f[x]) {
cir[++cn]=f[x];
BAN(fp[x]),cl+=(r[cn]=e[fp[x]].v);
}
for (int i=2;i<=cn;i++)
sum[i]=sum[i-1]+r[i];
r[1]=0;
for (int i=1;i<=cn;i++) {
mxdp=-1,findmx(i);
}
}
void let_s_be_a_big_role() {
plu.init(cn);
cha.init(cn);
plu.build(1,1,cn,sum,tree,1);
cha.build(1,1,cn,tree,sum,-1);
int x;long long tmp,ans2=inf;
for (int i=1;i<=cn;i++) {
if (plu.mxp[1]!=cha.mxp[1])
ans2=min(ans2,plu.mx[1]+cha.mx[1]);
else {
tmp=plu.mx[1]+cha.se[1];
if (plu.se[1]+cha.mx[1]>tmp)
tmp=plu.se[1]+cha.mx[1];
ans2=min(ans2,tmp);
}
plu.insert(1,1,cn,i,tree[i]+(cl+sum[i]));
cha.insert(1,1,cn,i,tree[i]-(cl+sum[i]));
}
ans=max(ans,ans2);
}
int main() {
// freopen("foodshop.in","r",stdin);
// freopen("foodshop.out","w",stdout);
fread(cp,1,6000000,stdin);
in(n);int x,y,v;
for (int i=1;i<=n;i++) {
in(x),in(y),in(v);
add(x,y,v),add(y,x,v);
}
circle();
let_s_be_a_big_role();
printf("%.1lf\n",(double)ans/2);
return 0;
}

留言