「LOJ 2669」「NOI2013」快餐店

发表于

小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。

快餐店的顾客分布在城市 C 的 NN 个建筑中，这 NN 个建筑通过恰好 NN 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。

现给定城市 C 的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。

Constraints

1≤n≤1000001\leq n \leq 100000

Solution

题目给出的图为一棵基环树。对于普通的树的情况，答案即为直径的 12\frac{1}{2} 。而对于基环树来说，答案有两种情况，经过环和不经过环。

对于不经过环的部分，我们可以直接树形 dp 求解。而对于经过环的部分，观察可得，一定有一条边没有经过，破环成链之后对应的就是一个区间。我们令 fif_i 为以 ii 为端点且另一个端点位于 ii 的子树中的最长链的长度，令 disi,jdis_{i,j} 表示破环成链后序列上 ii 和 jj 的距离，则最长链为 fi+disi,j+fjf_i+dis_{i,j}+f_j 。令 sis_i 表示序列上到 ii 的距离前缀和，则 disi,j=si−sjdis_{i,j}=s_i-s_j ，则最长链为 fi+si+fj−sjf_i+s_i+f_j-s_j 。对于一个区间，我们分别求出 fi+sif_i+s_i 和 fi−sif_i-s_i 的最大值即可。因为最大值有可能位于同一个位置，所以还需要维护次大值。在这里我们使用线段树进行维护。

关于统计答案时，序列上 jj 的位置一定在 ii 前面的证明，详见 《【树DP+基环树】[NOI2013]快餐店》 。

Code

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define lc (x<<1)
#define rc (x<<1|1)
#define LL long long
using namespace std;
const int N=1e5+5;
const LL inf=0x3f3f3f3f3f3f3f3f;
int n,x,y,w,vertex,tot,cnt=1;
int first[N],pre[N],edg[N],cir[N*2];
LL ans,f[N],g[N],s[N*2];
int L,R,cpos[2],pos[N*8][2];
LL cmx[2],cmn[2],mx[N*8][2],mn[N*8][2];
bool vis[N*2];
struct edge{int to,next,w;}e[N*2];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void insert(int u,int v,int w)
{
	e[++cnt]=(edge){v,first[u],w};first[u]=cnt;
	e[++cnt]=(edge){u,first[v],w};first[v]=cnt;
}
bool circle(int x,int last,int fa)
{
	if(pre[x]){pre[x]=fa;vertex=x;return true;}
	pre[x]=fa;
	for(int i=first[x];i;i=e[i].next)
	{
		if((i^1)==last)continue;
		int to=e[i].to;
		if(circle(to,i,x))
		{
			vis[i]=vis[i^1]=true;
			edg[to]=i;return true;
		}
	}
	return false;
}
void dfs(int x,int fa)
{
	LL mx=0,mn=0;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa||vis[i])continue;
		dfs(to,x);
		if(f[to]+e[i].w>mx)mn=mx,mx=f[to]+e[i].w;
		else if(f[to]+e[i].w>mn)mn=f[to]+e[i].w;
		g[x]=max(g[x],g[to]);
	}
	f[x]=mx;g[x]=max(g[x],mx+mn);
}
void update(int x,int p)
{
	if(mx[lc][p]>mx[rc][p])
	{
		mx[x][p]=mx[lc][p];pos[x][p]=pos[lc][p];
		mn[x][p]=max(mn[lc][p],mx[rc][p]);
	}
	else
	{
		mx[x][p]=mx[rc][p];pos[x][p]=pos[rc][p];
		mn[x][p]=max(mx[lc][p],mn[rc][p]);
	}
}
void build(int x,int l,int r,int p,int v)
{
	if(l==r)
	{
		mx[x][p]=f[cir[l]]+v*s[l];
		pos[x][p]=l;mn[x][p]=-inf;
		return;
	}
	int mid=(l+r)>>1;
	build(lc,l,mid,p,v);
	build(rc,mid+1,r,p,v);
	update(x,p);
}
void query(int x,int l,int r,int p)
{
	if(L<=l&&r<=R)
	{
		if(mx[x][p]>cmx[p])
		{
			cmn[p]=cmx[p];cmx[p]=mx[x][p];
			cpos[p]=pos[x][p];
		}
		else if(mx[x][p]>cmn[p])cmn[p]=mx[x][p];
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)query(lc,l,mid,p);
	if(R>mid)query(rc,mid+1,r,p);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		x=read();y=read();w=read();
		insert(x,y,w);
	}
	circle(1,0,-1);
	cir[++tot]=vertex;x=pre[vertex];
	while(x!=vertex){cir[++tot]=x;x=pre[x];}
	for(int i=1;i<=tot;i++)
	{
		dfs(cir[i],-1);ans=max(ans,g[cir[i]]);
		cir[tot+i]=cir[i];
	}
	LL cans=inf;
	for(int i=2;i<=tot*2;i++)
		s[i]=s[i-1]+e[edg[cir[i-1]]].w;
	build(1,1,tot*2,0,1);
	build(1,1,tot*2,1,-1);
	for(int i=1;i<=tot;i++)
	{
		L=i;R=i+tot-1;cpos[0]=cpos[1]=0;
		cmx[0]=cmx[1]=cmn[0]=cmn[1]=-inf;
		query(1,1,tot*2,0);query(1,1,tot*2,1);
		if(cpos[0]==cpos[1])cans=min(cans,max(cmx[0]+cmn[1],cmx[1]+cmn[0]));
		else cans=min(cans,cmx[0]+cmx[1]);
	}
	ans=max(ans,cans);
	printf("%.1lf",ans/2.0);
	return 0;
}