NOI2013 快餐厅

作为一道NOI题，这道题是一道好(难)题，这道题给了一张N点N边的图，让你在图中找一点到图中最远点最近，输出这个距最远点最近的距离，首先问题降低，如果这是一棵树，求一点到最远点的最短距离，那其实就是树的直径的一半，但是这道题是一颗环套树，所以现在分两种情况 ### 1 这个环套树的最长路径不经过环 这种情况是比较简单的，我们首先通过一些手段求出这个环，并记录环的信息，(方法：tarjan，dfs，并查集)；然后枚举每一个环上的点，对这些点下的子树求直径，取这些直径的最大值，记为ans1. 以上操作找环是O(n+m),对所有环上的点求子树是O(n)的，所以这一步总复杂度O(n+m); 时间复杂度的原因：每个点只便利了一次 ### 2 这个环套树的最长路径经过环 这种情况是比较复杂的，O(n * n) 60分算法是枚举环上的断点，是无法AC的，因此需要优化。 规定环上每个点为1--> circle_cnt A[i]表示(前缀链长度+当前换上节点子树最大深度) B[i]表示(前缀中两个点子树的最大深度+两点之间的距离) C[i]表示(后缀链长度+当前换上节点子树最大深度) D[i]表示(后缀中两个点子树的最大深度+两点之间的距离) 因此当我们枚举到断裂环上i与i+1点之间的边时， 答案为max(max(B[i],D[i]),A[i]+C[i+1]+(1-->circle_cnt点的边权))； 这个式子的含义是 取 max((前缀中的最大直径)，(后缀中的最大直径)，(前缀i与后缀i+1跨过1和circle_cnt点之间的边所组成的直径)) 显然的我们要保留这里求出的最小值，因为这里求出的路径是所有路径都有可能，不一定是两点间的最短路，这里我就有疑问，但就像第一个样例，最长的路是3->1->4->2距离为5，事实上有3->1->2->4距离为4的路存在，这样无疑缩短了求的直径。 记这个最小值为ans2.这个步骤复杂度时O(circle_cnt) 最终输出max(ans1,ans2)/2; How interesting it is! 以上就是主要思路，对于经过环上的路径也可以通过线段树来求，但是没有这种方法更优。 代码如下 ~~~ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<cmath> #include<map> using namespace std; typedef long long ll; const int maxn=100000+10; const int inf=0x3f3f3f3f; const int mod=1e9+7; int n; struct Edge{ int to,from,cost; }edge[maxn<<1]; int last[maxn<<1],cnt=0; int huan[maxn],huan_cnt=0,huan_zhi[maxn],fa[maxn],cost[maxn],huan_sign[maxn]; int dfn[maxn],timee=0; ll dis[maxn]; ll ans=0,ans1=0; ll A[maxn],B[maxn]; //A[i]表示 前缀中最大的一条链+当前节点树的最大深度 //B[i]表示前缀中两棵树的最大深度+这两个节点间的距离 ll C[maxn],D[maxn]; //这是后缀做的 //因此当断换上第i与i+1条边时 ans=max(max(B[i],D[i+1]),A[i]+C[i+1]+1-->cnt的边权和) inline int read(){ int a=1,b=0;char c=getchar(); while(c>'9'||c<'0'){if(c=='-') a=-1;c=getchar();} while(c>='0'&&c<='9'){b=(b<<3)+(b<<1)+c-'0';c=getchar();} return a*b; } inline void print(ll x){ if(x<0) x=-x,putchar('-'); if(x>9) print(x/10); putchar(x%10+'0'); } inline void pre(){ } inline void add(int x,int y,int z){ edge[++cnt].to=y; edge[cnt].cost=z; edge[cnt].from=last[x]; last[x]=cnt; } inline void input(){int xx,yy,zz; n=read(); for(int i=1;i<=n;++i) { fa[i]=i; xx=read(),yy=read(),zz=read(); add(xx,yy,zz); add(yy,xx,zz); } } inline void dfs(int now){//此处找环并记录 dfn[now]=++timee; for(int i=last[now];i;i=edge[i].from) { int to=edge[i].to; if(to!=fa[now]) { if(!dfn[to]) { fa[to]=now; cost[to]=edge[i].cost; dfs(to); } else if(dfn[to]>dfn[now]) { for(;to!=now;to=fa[to]) { huan_sign[to]=1; huan[++huan_cnt]=to; huan_zhi[huan_cnt]=cost[to]; } huan_sign[now]=1; huan[++huan_cnt]=now; huan_zhi[huan_cnt]=edge[i].cost; } } } } inline void DP(int now,int father){//dis[i]表示i所在的子树上的直径 for(int i=last[now];i;i=edge[i].from) { int to=edge[i].to; if(!huan_sign[to]&&to!=father) { DP(to,now); ans=max((ll)dis[now]+dis[to]+edge[i].cost,ans); dis[now]=max(dis[now],dis[to]+edge[i].cost); } } } inline void solve(){ dfs(1); for(int i=1;i<=huan_cnt;++i) DP(huan[i],0); ll sum=0,maxx=0; for(int i=1;i<=huan_cnt;++i) { sum+=huan_zhi[i-1]; A[i]=max(A[i-1],dis[huan[i]]+sum); B[i]=max(B[i-1],sum+maxx+dis[huan[i]]); maxx=max(maxx,dis[huan[i]]-sum); } sum=maxx=0; int tmp=huan_zhi[huan_cnt];huan_zhi[huan_cnt]=0; for(int i=huan_cnt;i>=1;--i) { sum+=huan_zhi[i]; C[i]=max(C[i+1],dis[huan[i]]+sum); D[i]=max(D[i+1],sum+maxx+dis[huan[i]]); maxx=max(maxx,dis[huan[i]]-sum); } ll tep; ans1=B[huan_cnt]; for(int i=1;i<huan_cnt;++i) { tep=max(B[i],D[i+1]); tep=max(tep,A[i]+C[i+1]+tmp); ans1=min(tep,ans1); } ans=max(ans,ans1); if(ans&1) print(ans>>1),puts(".5"); else print(ans>>1),puts(".0"); } inline void output(){ } int main(){int T; T=1; while(T--) { pre(); input(); solve(); output(); } return 0; } ~~~