首页 > 代码库 > UOJ#126【NOI2013】快餐店

UOJ#126【NOI2013】快餐店

2024-09-30 05:55:39   219人阅读

【NOI2013】快餐店

链接：http://uoj.ac/problem/126

YY了一个线段树+类旋转卡壳的算法。骗了55分。还比不上$O(n^2)$暴力T^T

题目实际上是要找一条链的两个端点，链的中点处建快餐店。要求这两个端点的最短距离为其他所有点对的最短距离的最大值。

  1. 这条链不经过环，那答案就是环上挂的某个子树的子树直径。至少大于等于最大的树直径。树DP一发得到Ans1
  2. 经过环，显然不会饶环一圈。这个链必定由这样构成：x,y为环上两点。x子树最长链->x-y最短路-y子树最长链。可以枚举断掉一条边，然后求树的直径。取min。

第二种情况具体做法：枚举环上的边i-i+1。$定义S_U(x)表示S_U(x)+sum[x]为到1的最长链，\\ P_U(x)表示P_U+sum[n]-sum[x]为到1的最长链即环的另一侧。\\ S_V(x)表示前缀到x的最长链+x子树最长链，P_V(x)表示后缀的。sum[i]为环上前i条边的边权和$

　　直径$=max\{S_U(i)+P_U(i+1)+sum[n]-当前该边边权,S_v(i),P_V(i+1)\}$ Ans2=min{Ans2,直径}

$Ans=\frac{max\{Ans1,Ans2\}}{2.0}.$

然后有一些细节，建议自己画画图分析下。

#include<cmath>#include<cstdio>typedef long long ll;template<class T>inline void read(T&x){    x=0;bool f=0;char c=getchar();    while((c<‘0‘||c>‘9‘)&&c!=‘-‘)c=getchar(); if(c==‘-‘)f=1,c=getchar();    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    x=f?-x:x;}const int MAXN(100010),LEN(200010);const ll INF(0x7fffffffffffffff);int n,a[MAXN],b[MAXN],l[MAXN];struct Node{int nd,nx,co;}bot[MAXN<<1];int tot,first[MAXN];void add(int a,int b,int c){bot[++tot]=(Node){b,first[a],c};first[a]=tot;}int st[MAXN],pos[MAXN],last[MAXN],tp;bool bf[MAXN],vis[MAXN];int Ring[LEN],dis[LEN],Rsize;void DFS(int x,int f){    st[++tp]=x;pos[x]=tp;    for(int v=first[x];v;v=bot[v].nx)    if(bot[v].nd!=f)    {        if(pos[bot[v].nd])        {            if(dis[1])continue;            for(int i=pos[bot[v].nd];i<=tp;i++)            {                Ring[++Rsize]=st[i];bf[st[i]]=1;                dis[Rsize]=last[st[i]];            }            dis[1]=bot[v].co;        }else         {            last[bot[v].nd]=bot[v].co;            DFS(bot[v].nd,x);        }    }    --tp;pos[x]=0;}void umax(ll &a,ll b){if(a<b)a=b;}ll max(ll a,ll b){return a>b?a:b;}ll min(ll a,ll b){return a<b?a:b;}ll lm[MAXN],Ans,Ans2,all;void DP(int x){    bf[x]=1;    for(int v=first[x];v;v=bot[v].nx)    if(!bf[bot[v].nd])    {        DP(bot[v].nd);        umax(Ans,lm[x]+lm[bot[v].nd]+bot[v].co);        umax(lm[x],lm[bot[v].nd]+bot[v].co);    }}ll Sv[MAXN],Su[MAXN],Pv[MAXN],Pu[MAXN],Sd[MAXN],Pd[MAXN];void Get_Ring(){    Ring[Rsize+1]=Ring[1];dis[Rsize+1]=dis[1];    for(int i=1;i<=Rsize;i++)    {        Sv[i]=(i!=1)?Sd[i-1]+dis[i]+lm[Ring[i]]:lm[Ring[i]];        umax(Sv[i],Sv[i-1]);        Sd[i]=(i!=1)?max(Sd[i-1]+dis[i],lm[Ring[i]]):lm[Ring[i]];        Su[i]=max(Su[i-1]-dis[i],lm[Ring[i]]);        all+=dis[i];    }    for(int i=Rsize+1;i>1;i--)    {        Pv[i]=(i!=Rsize+1)?Pd[i+1]+dis[i+1]+lm[Ring[i]]:lm[Ring[i]];        umax(Pv[i],Pv[i+1]);        Pd[i]=(i!=Rsize+1)?max(Pd[i+1]+dis[i+1],lm[Ring[i]]):lm[Ring[i]];        if(i!=Rsize+1)Pu[i]=max(Pu[i+1]-dis[i+1],lm[Ring[i]]);         //以防lm[Ring[1]]被加两次     }    Ans2=INF;    for(int i=1;i<=Rsize;i++)        Ans2=min(Ans2,max(max(Sv[i],Pv[i+1]),Su[i]+Pu[i+1]+all-dis[i+1]));}int main(){//    freopen("C.in","r",stdin);//    freopen("C.out","w",stdout);    read(n);    for(int i=1;i<=n;i++)    {        read(a[i]),read(b[i]),read(l[i]);        add(a[i],b[i],l[i]),add(b[i],a[i],l[i]);    }    DFS(1,0);    for(int i=1;i<=n;i++)if(bf[i])DP(i);    Get_Ring();    umax(Ans,Ans2);    printf("%.1lf",(Ans+0.05)/2.0);    return 0;}

 

UOJ#126【NOI2013】快餐店


联系
我们