P1399 [NOI2013] 快餐店 题解

xiaolangwhite · 2023-07-19 11:43:46 · 题解

这是我的第一篇题解，感谢大家的食用。

码风稍丑，望诸位大佬勿喷。

题意解读

你有一颗基环树，现在想让你找一个点，使得这个点（不一定在节点上）到所有点的距离中最大距离最短。

分析：

答案即为基环树的直径的一半。

证明：

由基环树的直径定义可得：

直径上的两个端点在基环树上有最长距离（否则就不是直径了）。

那么如果我们要求某个点到所有点的距离中最大距离最短。

自然可得在直径的中点处，得最大距离最短。

证毕。

解题思路

接下来就因该看如何实现求直径的操作了。

对于一颗基环树，其本质上是一颗（或多颗树）+ 环（有却只有一个）构成。

那么，我们只需把环找出断开并特殊处理，我们就可以把基环树当成树对待。

（基环树常见套路）。

代码过程

代码编译环境： GNU C++ 11

存图

我们以链式前向星存边（链式前向星的 u 可以不要）。

struct Edge {
    ll u,v,w,nxt;
} edge[MAXN];
ll cnt,head[MAXN];
void AddEdge(ll u,ll v,ll w) {
    edge[++cnt] = {u,v,w,head[u]},head[u] = cnt;
}

判断环

定义数组：

#define ll long long
ll father[MAXN],val[MAXN];
ll ringlength[MAXN],ring[MAXN],ringcnt,ringroot;
bool inring[MAXN];
ll length[MAXN];
ll dfn[MAXN],ct;

（为什么要记录呢？因为在调用时可以更快更方便，且通往这个节点的 father_{i} 不只是一个，记录下来以防弄错）。

tarjan 判断环

void dfs(ll x) {
    dfn[x] = ++ct;
    ll v,w;
    for(ll i = head[x]; i; i=edge[i].nxt) {
        v = edge[i].v,w = edge[i].w;
        if(v != father[x]) {
            if(!dfn[v]) {
                val[v] = w,father[v] = x;
                dfs(v);
            } else if(dfn[x] < dfn[v]) {
                for(ll i = v; i != x; i = father[i]) {
                    inring[i] = 1,ring[++ringcnt] = i,ringlength[ringcnt]=val[i];
                }
                inring[x] = 1,ring[++ringcnt] = x,ringlength[ringcnt]=edge[i].w;
            }
        }
    }
}

不会的自行补学一下 tarjan。

重点解释一下 if 中的内容。

if(v != father[x]) {
    if(!dfn[v]) {
        val[v] = w,father[v] = x;
        dfs(v);
    } else if(dfn[x] < dfn[v]) {
        for(ll i = v; i != x; i = father[i]) {
            inring[i] = 1,ring[++ringcnt] = i,ringlength[ringcnt]=val[i];
        }
        inring[x] = 1,ring[++ringcnt] = x,ringlength[ringcnt]=edge[i].w;
}

在没有利用双向边回到自己父亲节点时：

判断新节点是否被经过。

如果未被经过，则将边权和将搜的点的 father_{i} 记录下来。

边权不会错是应为如果没发现环，回溯过来时边权会重新被覆盖， father_{i} 数组同理。

在进一步进行深搜：

如果发现更晚的时间戳（即证明已经经过），则等价于发现环。

在由于之前的 father_{i} 已被记录，最终可以遍历环，把环储存下来（不要忘了自己）。

统计所有子树最大高度

ll res1,res2;//统计所有子树最大高度 
void statistics(ll x,ll fa){
    ll v,w;
    for(int i = head[x];i;i = edge[i].nxt){
        v = edge[i].v,w = edge[i].w;
        if(!inring[v]&&v != fa){
            statistics(v,x);
            res1 = max(res1,length[x]+length[v]+w);
            length[x] = max(length[x],length[v]+w);
        }
    }
}

也是重点解释 if 中的部分：

if(!inring[v]&&v != fa){
    statistics(v,x);
    res1 = max(res1,length[x]+length[v]+w);
    length[x] = max(length[x],length[v]+w);
}

如果不在环上，进行搜索，统计一棵子树的最大直径。

当加上如下代码时：

for(int i = 1;i <= ringcnt;i++){
    statistics(ring[i],0);
}

则是统计所有子树的最大直径 res1 。

而 length_{i} 则表示长度记录，不断更新，获得从这个点下去子树的最大深度。

准确来讲叫距离，所以叫 length 。

重点分割线 qwq

对于直径的求解

ll sum,maxx,tmp;
ll A[MAXN],B[MAXN],C[MAXN],D[MAXN];
void init(){
    for(int i = 1;i <= ringcnt;i++){
        sum += ringlength[i-1];
        A[i] = max(A[i-1],length[ring[i]]+sum);
        B[i] = max(B[i-1],sum+maxx+length[ring[i]]);
        maxx = max(maxx,length[ring[i]]-sum);
    }
    sum = maxx = 0;
    tmp = ringlength[ringcnt];
    ringlength[ringcnt] = 0;
    for(int i = ringcnt;i>=1;i--){
        sum += ringlength[i];
        C[i] = max(C[i+1],length[ring[i]]+sum);
        D[i] = max(D[i+1],sum+maxx+length[ring[i]]);
        maxx = max(maxx,length[ring[i]]-sum);
    }
}
init();
res2 = B[ringcnt];
for(int i = 1;i <= ringcnt;i++){
    res2 = min(max(A[i]+C[i+1]+tmp,max(B[i],D[i+1])),res2);
}
printf("%.1f",double(max(res1,res2)/2.0));//注意整除

我们规定：