【BZOJ3242】【NOI2013】快餐店（动态规划）

题面

BZOJ

题解

假设我们要做的是一棵树，那么答案显然是树的直径的一半。

证明？

假设树的直径是\(2d\)，那么此时最远点的距离是\(d\)

假设存在一个点的距离大于\(d\)，那么直径可以由这个点到达直径的一个端点拼出。

所以最远点距离为\(d\)。

现在的问题在基环树上。

可以用\(dp\)求出所有外向树上的直径以及能够一直向下延伸的最大深度\(f[i]\)。

显然最终在基环树上的答案一定只会经过基环树的一部分，

也就是如果从某条不在答案的路径上，把它断开，对于答案没有任何影响。

那么考虑枚举从哪个位置断开，然后维护一下最长链就好了。

我们把环上的点顺次放在一排，然后编号\(1..m\)

假设\(1->2->3->...->x\)的链长度为\(W[x]\)

那么最长链就是\(max(f[i]+f[j]+W[j]-W[i]),i\lt j\)

每次枚举断点，然后扫一遍求最大值，这样子的复杂度是\(O(n^2)\)的。

然后就是一堆奇奇怪怪的优化了，感觉我自己都说不清。

因为我是照着别人写的了 。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 111111

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

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

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line{int v,next,w;}e[MAX<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

bool cir[MAX];

int p[MAX<<1],top,dep[MAX],fa[MAX],n;

ll f[MAX],ans,W[MAX<<1],Cir=1e18,pre1[MAX],pre2[MAX],l1[MAX],l2[MAX];

int Q[MAX<<1],H,T;

void findcir(int u,int ff)

{

	dep[u]=dep[ff]+1;fa[u]=ff;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		if(dep[v]&&dep[v]>dep[u])

		{

			for(int j=v;j!=u;j=fa[j])cir[j]=true,p[++top]=j;

			p[++top]=u;cir[u]=true;continue;

		}

		if(!dep[v])findcir(v,u);

	}

}

void dfs(int u,int ff)

{

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff||cir[v])continue;

		dfs(v,u);ans=max(ans,f[u]+f[v]+e[i].w);

		f[u]=max(f[u],f[v]+e[i].w);

	}

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)

	{

		int u=read(),v=read(),w=read();

		Add(u,v,w);Add(v,u,w);

	}

	findcir(1,0);

	for(int i=1;i<=top;++i)dfs(p[i],0);p[top+1]=p[1];

	for(int i=1;i<=top;++i)

		for(int j=h[p[i]];j;j=e[j].next)

			if(e[j].v==p[i+1]){W[i]=e[j].w;break;}p[top+1]=0;

	ll sum=0,mx=0;

	for(int i=1;i<=top;++i)

	{

		sum+=W[i-1];pre1[i]=max(pre1[i-1],f[p[i]]+sum);

		l1[i]=max(l1[i-1],f[p[i]]+mx+sum);

		mx=max(mx,f[p[i]]-sum);

	}

	ll tot=W[top];W[top]=sum=mx=0;

	for(int i=top;i;--i)

	{

		sum+=W[i];pre2[i]=max(pre2[i+1],f[p[i]]+sum);

		l2[i]=max(l2[i+1],f[p[i]]+mx+sum);

		mx=max(mx,f[p[i]]-sum);

	}

	Cir=l1[top];

	for(int i=1;i<top;++i)

		Cir=min(Cir,max(max(l1[i],l2[i+1]),pre1[i]+pre2[i+1]+tot));

	ans=max(ans,Cir);

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

	return 0;

}