首页 > 代码库 > [noi2013]快餐店 基环树dp,单调队列维护最大值和次大值
[noi2013]快餐店 基环树dp,单调队列维护最大值和次大值
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 220000#define inf 0x3ffffffffffffffLLtypedef long long ll;int v[N],e[N],ne[N],nn,w[N];void add(int x,int y,int z){ ne[++nn]=e[x],e[x]=nn,v[nn]=y,w[nn]=z;}int n;int dfn[N];int tot;int fa[N],ww[N*2],f2[N];int bb,b1[N*2];ll ss[N*2];void dfs(int x){ dfn[x]=++tot; for(int i=e[x];i;i=ne[i]){ if(fa[x]==v[i])continue; if(!dfn[v[i]]){ fa[v[i]]=x; f2[v[i]]=w[i]; dfs(v[i]); }else{ if(dfn[v[i]]>dfn[x]){ for(int j=v[i];j!=x;j=fa[j]){ b1[++bb]=j; ww[bb]=f2[j]; } b1[++bb]=x; ww[bb]=w[i]; } } }}int been[N];ll dp1[N],dp2[N];ll ans2;int q1[N*2],he1,bo1;int q2[N*2],he2,bo2;ll v1[N*2],v2[N*2];void dfs2(int x,int fa){ for(int i=e[x];i;i=ne[i]){ if(fa==v[i]||been[v[i]])continue; dfs2(v[i],x); ans2=max(ans2,dp1[x]+dp1[v[i]]+w[i]); dp1[x]=max(dp1[x],dp1[v[i]]+w[i]); }}ll ma;void gg(int x,int y){ if(q1[x]!=q2[y]){ ma=max(ma,v1[x]+v2[y]); }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } dfs(1); for(int i=1;i<=bb;i++)been[b1[i]]=1; for(int i=1;i<=bb;i++){ dfs2(b1[i],0); } for(int i=1;i<=bb;i++)ww[i+bb]=ww[i],b1[i+bb]=b1[i]; for(int i=1;i<=bb*2;i++)ss[i]=ss[i-1]+(ll)ww[i]; ll ans=inf; q1[he1=bo1=1]=1; q2[he2=bo2=1]=1; q1[++he1]=2; q2[++he2]=2; for(int i=3;i<=bb*2;i++){ if(i-q1[bo1]>=bb)bo1++; if(i-q2[bo2]>=bb)bo2++; ma=0; while(he1>bo1+1&&v1[he1]>v1[he1-1]){ swap(v1[he1],v1[he1-1]); swap(q1[he1],q1[he1-1]); he1--; } while(he2>bo2+1&&v2[he2]>v2[he2-1]){ swap(v2[he2],v2[he2-1]); swap(q2[he2],q2[he2-1]); he2--; } q1[++he1]=i; q2[++he2]=i; v1[he1]=dp1[b1[i]]+ss[i-1]; v2[he2]=dp1[b1[i]]-ss[i-1]; if(i>bb){ gg(bo1,bo2); gg(bo1,bo2+1); gg(bo1,he2); gg(bo1+1,bo2); gg(bo1+1,bo2+1); gg(bo1+1,he2); gg(he1,bo2); gg(he1,bo2+1); ans=min(ans,ma); } } ans=max(ans,ans2); if(ans%2LL==0LL){ printf("%lld.0",ans/2LL); }else{ printf("%lld.5",ans/2LL); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。