【Noi2013】快餐店

Source and Judge

Noi2013
bzoj3242

Record

2h

Analysis

请先思考后再展开

第一次写基环树(以前总觉得好麻烦啊不想写什么的……)
这次写是没事干练练码力

如果是一棵树,那么一定是找直径的中点
但在基环树上,直径的许多性质被破坏了,不能直接求图的直径
考虑把基环树转化为树,首先断掉一条边不会使答案更优,而且一定有一条边去掉不会有影响(考虑对最优点到各个点的路径一定是树)

把环拉成序列,然后答案的下界是max 各个树内直径/2,而且断边不会影响这个,先处理好,最后更新ans
然后设我们枚举的断边,右边的节点编号为k=1~cnt-1(从0开始)
然后分情况讨论直径经过环上边的情况,是在断边左边a、右边c或者从右边开始去往左边b
$$
\begin{aligned}
val是挂在这上面的树的最大深度,d是前缀环上距离\
A1(i)=&前缀max的val-d\
B1(i)=&后缀max的val-d\
B2(i)=&后缀max的val+d\
0<i<k,a=&A1(i-1)+d_i+val_i\
0 \leq i<k,b=&B1(k)+d_i+d_{cnt-1}+d_{cnt-1到0}+val_i\
k \leq i<cnt,c=&B2(i+1)-d_i+val_i\
ans=&min(ans,max(a,b,c))
\end{aligned}
$$

那么显然可以 O(n) 做了

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const ll INF=1ll<<60;
// #define pr pair<int,int>
// #define FR first
// #define SE second
// #define MP make_pair
const int MAX_N=1e5+10;
int hou[MAX_N];bool v[MAX_N];
struct Edge{int y,c,g;}e[MAX_N*2];
int ln=0;void ins(int x,int y,int c) {e[++ln]=(Edge){y,c,hou[x]};hou[x]=ln;}
stack<int> sta;bool in[MAX_N];
vector<int> id;
bool dfs(int x,int fa)
{
if(in[x])
{
while(1)
{
int now=sta.top();sta.pop();
id.push_back(now);v[now]=1;
if(now==x) break;
}
return 1;
}
in[x]=1,sta.push(x);
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
if(dfs(y,x)) return 1;
}
in[x]=0;sta.pop();
return 0;
}
ll f[MAX_N],zjmx=0;
void getzj(int x,int fa)
{
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa or v[y]) continue;
getzj(y,x);zjmx=max(zjmx,f[x]+f[y]+e[k].c);
f[x]=max(f[x],f[y]+e[k].c);
}
}
ll d[MAX_N],val[MAX_N];
ll A1[MAX_N],B1[MAX_N],B2[MAX_N];
struct Nod{ll d;int p;}tmp[MAX_N];bool cmp(Nod a,Nod b){return a.d>b.d;}
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
ins(a,b,c);ins(b,a,c);
}
dfs(1,0);int cnt=id.size();
for(int i=0;i<cnt;i++)
{
if(i!=0) for(int k=hou[id[i]];k>0;k=e[k].g) if(e[k].y==id[i-1]) d[i]=e[k].c;
d[i]+=d[i==0?0:i-1];getzj(id[i],0);val[i]=f[id[i]];
}
for(int k=hou[id[0]];k>0;k=e[k].g) if(e[k].y==id[cnt-1]) d[cnt]=e[k].c;
A1[0]=val[0]-d[0];for(int i=1;i<cnt;i++) A1[i]=max(A1[i-1],val[i]-d[i]);
B1[cnt]=B2[cnt]=-INF;
for(int i=cnt-1;i>=0;i--) B1[i]=max(B1[i+1],val[i]-d[i]),B2[i]=max(B2[i+1],val[i]+d[i]);
for(int i=0;i<=cnt-2;i++) tmp[i]=(Nod){B2[i+1]-d[i]+val[i],i};
sort(tmp,tmp+cnt-1,cmp);
ll ans=INF,A=-INF,B=d[0]+val[0];
for(int k=1,now=0;k<cnt;k++)
{
ll a=A,b=B1[k]+d[cnt-1]+d[cnt]+B;
while(now!=cnt-1 and tmp[now].p<k) now++;
ll c=(now==cnt-1?-INF:tmp[now].d);
ans=min(ans,max(a,max(b,c)));
A=max(A,A1[k-1]+d[k]+val[k]);
B=max(B,d[k]+val[k]);
}
ans=min(ans,A);//断0->cnt-1
printf("%.1lf",max(zjmx,ans)/2.0);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/e514.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%