bzoj1999 (洛谷1099) 树网的核—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1999

　　　 https://www.luogu.org/problemnew/show/P1099

“分析性质，O(n)扫描”

看了半天才懂...发现自己对树的直径的相关知识太不熟了...

这篇博客的讲解很详细：https://www.cnblogs.com/shenben/p/5895325.html

说一下自己的理解：

1.每个直径对答案的贡献是相同的；

因为所有直径都相交，所以不妨考虑公共部分和分叉部分；

会发现分叉部分的答案不如公共部分优，因为我们要取最小的偏心距，而分叉部分的偏心距一定会覆盖公共部分；

所以只需要找出一条直径来做；

2.一条直径上找最小偏心距，一定在“核”最长的时候找；

这个很容易想到，因为长“核”一定不会劣于短“核”；

3.对于一个“核”，有三个值可以更新它的偏心距：

①直径上的两端到“核”的两端的两个距离；

②“核”上所有点到直径外子树的最长距离；

其中的①，许多“核”会重复求同样的值，所以干脆把它扩展到整条直径上的点到直径外子树的最大距离，求一遍即可；

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int const maxn=;

int n,s,head[maxn],ct,dis[maxn],fa[maxn],l,l2;

bool vis[maxn];

struct N{

    int to,next,w;

    N(int t=,int n=,int w=):to(t),next(n),w(w) {}

}edge[maxn<<];

void add(int x,int y,int z){edge[++ct]=N(y,head[x],z); head[x]=ct;}

int rd()

{

    int ret=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

    while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

    return ret*f;

}

void dfs(int x)

{

    for(int i=head[x];i;i=edge[i].next)

    {

        int u=edge[i].to;

        if(vis[u]||u==fa[x])continue;

        dis[u]=dis[x]+edge[i].w;

        fa[u]=x; dfs(u);

    }

}

int main()

{

    n=rd(); s=rd();

    for(int i=,x,y,z;i<n;i++)

    {

        x=rd(); y=rd(); z=rd();

        add(x,y,z); add(y,x,z);

    }

    l=; l2=;

    dis[l]=; fa[l]=; dfs(l);

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

        if(dis[i]>dis[l])l=i;

    dis[l]=; fa[l]=; dfs(l);

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

        if(dis[i]>dis[l2])l2=i;

    int ans=0x3f3f3f3f,j=l2;

    for(int i=l2;i;i=fa[i])

    {

        while(fa[j]&&dis[i]-dis[fa[j]]<=s)j=fa[j];

        ans=min(ans,max(dis[j],dis[l2]-dis[i]));//min,max

    }

    for(int i=l2;i;i=fa[i])vis[i]=;

    for(int i=l2;i;i=fa[i])dis[i]=,dfs(i);

    for(int i=;i<=n;i++)ans=max(ans,dis[i]);//max

    printf("%d",ans);

    return ;

}

巴特西

bzoj1999 (洛谷1099) 树网的核——dfs

最新文章

热门文章