UOJ #126 【NOI2013】快餐店

题目链接：快餐店

　　震惊！某ZZ选手此题调了一天竟是因为……>>点击查看

　　一般碰到这种基环树的题都要先想想树上怎么做。这道题如果是在树上的话……好像求一遍直径就做完了？答案就是直径长度的一半……

　　然后我们来考虑一下基环树上的情况。假设我们选中了一个位置\(u\)作为快餐店，那么环上的有一条边是没有用的，也就是说\(u\)到其它所有点的最短路都不会经过这条边。于是，我们就可以枚举删掉环上每条边，就需要快速统计剩下这棵树的直径。如果这课树的直径没有经过环上的边，那么我们是可以通过预处理环上每棵树的直径来得到的。于是，我们接下来只考虑直径经过换上的边的情况。

　　为了方便讲述，假设环上的点的编号为\(1\)到\(m\)，\(1\)到\(x\)的边权和为\(w_x\)。首先，我们需要预处理环上每个点\(u\)为根往下的最长链\(f_u\)。然后，我们其实预处理几个数组即可(这里只考虑前缀)，包括\(pre_i\)，表示环上只用\([1,i]\)这些点组成的最长的链。由于\(pre_i=\max\{f_u+f_v+w_u-w_v\}(u>v)\)，所以我们还需要维护一下\(f_x+w_x\)，\(f_x-w_x\)的前缀最大值，然后每次更新即可。注意为了避免选出了两个重复的点，可以每次使用\(f_u+w_u+\max\{f_v-w_v\}(v<u)\)和\(pre_{u-1}\)来更新\(pre_u\)。类似的可以对后缀求出对应的数组。

　　然后，我们在枚举环上断哪条边的时候只需要分三种情况讨论即可。假设我们断了边\((u,u+1)\)，那么假设环上最优的两个点为\(i，j(i<j)\)，那么要么\(1 \le i < j \le u\)，要么\(u+1 \le i < j \le m\)，还有\(1\le i \le u\)且\(u+1\le j \le m\)。分别用我们预处理出来的结果算出来，取个\(\max\)就是直径。最后把所有直径的\(\min\)和不过环的直径取个\(\max\)就是最终答案的两倍。

　　然后我递归的时候函数名打错了……然后就到了另外一个函数里面去了……然后一天就这么过去了(捂脸

　　你不要说我开头那个链接是在骗你吗……你看这里不是讲了原因么→_→

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);

#define maxn 100010

#define maxm 200010

#define INF (1LL<<60)

using namespace std;

typedef long long llg;

int head[maxn],next[maxm],to[maxm],c[maxm],tt;

int n,m,fa[maxn],dfn[maxn],a[maxn];

llg dep[maxn],ans,f[maxn],b[maxn];

llg su[maxn],pr[maxn],qi[maxn][2],ho[maxn][2];

bool vis[maxn];

int getint(){

	int w=0,q=0;

	char c=getchar();

	while((c>'9'||c<'0')&&c!='-') c=getchar();

	if(c=='-') q=1,c=getchar();

	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

	return q?-w:w;

}

void link(int x,int y){

	to[++tt]=y;next[tt]=head[x];head[x]=tt;

	to[++tt]=x;next[tt]=head[y];head[y]=tt;

	c[tt-1]=c[tt]=getint();

}

void work(int rt,int u){

	while(u!=fa[rt]){

		a[++m]=u; vis[u]=1; u=fa[u];

		b[m+1]=dep[a[m]]-dep[u];

	}

	for(int i=1;i<=m;i++) b[i]+=b[i-1];

}

void dfs(int u){

	dfn[u]=++tt;

	for(int i=head[u],v;v=to[i],i;i=next[i])

		if(v!=fa[u] && !dfn[v]){

			dep[v]=dep[u]+c[i];

			fa[v]=u,dfs(v);

		}

	for(int i=head[u],v;v=to[i],i;i=next[i])

		if(fa[v]!=u && dfn[v]>dfn[u]) b[1]=c[i],work(u,v);

}

void dp(int u){

	vis[u]=1;

	for(int i=head[u],v;v=to[i],i;i=next[i])

		if(!vis[v]){

			dp(v); ans=max(ans,f[u]+f[v]+c[i]);

			f[u]=max(f[u],f[v]+c[i]);

		}

}

void solve(){

	qi[0][0]=ho[m+1][0]=pr[0]=-INF;

	qi[0][1]=ho[m+1][1]=su[m+1]=-INF;

	for(int i=1,u;u=a[i],i<=m;i++){

		qi[i][0]=max(qi[i-1][0],f[u]+b[i]-b[1]);

		qi[i][1]=max(qi[i-1][1],f[u]-b[i]+b[1]);

		pr[i]=max(pr[i-1],f[u]+b[i]-b[1]+qi[i-1][1]);

	}

	for(int i=m,u;u=a[i],i>=1;i--){

		ho[i][0]=max(ho[i+1][0],f[u]-b[i]+b[m]);

		ho[i][1]=max(ho[i+1][1],f[u]+b[i]-b[m]);

		su[i]=max(su[i+1],f[u]-b[i]+b[m]+ho[i+1][1]);

	}

	llg g=pr[m],now=0;

	for(int i=1;i<m;i++){

		now=b[1]+qi[i][0]+ho[i+1][0];

		now=max(now,max(pr[i],su[i+1]));

		g=min(g,now);

	}

	ans=max(ans,g);

}

int main(){

	File("a");

	n=getint();

	for(int i=1;i<=n;i++) link(getint(),getint());

	tt=0; dfs(1);

	for(int i=1;i<=m;i++) dp(a[i]);

	solve();

	printf("%.1lf",ans/2.0);

	return 0;

}

　　BZOJ提交网址：BZOJ 3242 快餐店

巴特西

UOJ #126 【NOI2013】快餐店

最新文章

热门文章

巴特西

UOJ #126 【NOI2013】 快餐店

最新文章

热门文章

UOJ #126 【NOI2013】快餐店