【NOI2013】快餐店

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

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

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

这条链不经过环，那答案就是环上挂的某个子树的子树直径。至少大于等于最大的树直径。树DP一发得到Ans1
经过环，显然不会饶环一圈。这个链必定由这样构成：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<cstdio>

#include<algorithm>

typedef long long ll;

template

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】快餐店

【NOI2013】快餐店

最新文章

热门文章