BZOJ 3242 - [Noi2013]快餐店

#基环树 #基环树上最长链

Published on 2016-05-21

题目地址

描述

UOJ 传送门：【NOI2013】快餐店

分析

如果是一棵树，最优点在直径的 $\frac 1 2 d$ 处。
证明：不可能有点到这个点的距离大于 $\frac 1 2 d$ ，否则直径会大于 $d$ ，矛盾。

不加证明的给出一个结论：基环树的基环上存在一条边，使得基环树上的任意点对均有一条最短路不经过此边。

所以我们去掉这一条边，对任意点对的最短路没有任何影响！问题转化为树的情形，求出直径解决。由于去掉的是基环上的边，而直径可能存在于外向树上面，我们先求出所有外向树的最大直径 $l_1$ ，以及每个基环上的点向下延伸的最长距离 $d_i$ 。
根据这个性质，我们依次枚举基环上的每条边，记最短的直径为 $l$ （但如果有多个最小直径，仍然无法区分谁是这条边，但题目不要求知道这条边）。则答案为 $\frac{\max (l, l_1)} 2$ 。

问题是，依次去掉某条边后，如何快速求出直径呢？拆环为链，设环上有 $k$ 个节点，则我们拆为 $2k$ 个节点的链，方便处理顺时针和逆时针的情况：

链中 $u \rightarrow v$ 的边就是环上 $u \rightarrow v$ 的边，例如 4 到 1 的边就是环上 4 到 1 的边。设 $s_i$ 为节点 $i$ 到链起点的长度。
则我们要做的就是分别截取 $k$ 个长度为 $k$ 的区间，等价于依次删除 $k$ 条边。找到最长链也就是这个区间内下式的最大值：

s_i - s_j + d_i + d_j = (s_i + d_i) + (-s_j + d_j) (j < i)

麻烦的是 $j < i$ 这个限制，如果没有的话直接分别取两个括号的最值就好了。其实这个限制可以忽略，原因是假设 $j > i$ ，那么交换 $i, j$ 只会使值更大。但是这样做，仍然面临一个问题，就是，两个括号的最值都由 $i$ 取到是不合法的，所以我们必须记录最大值和次大值的位置，再算最值才行，但这样太麻烦了。

稍作思考可以发现一个神奇的性质， $(s_i + d_i) + (-s_j + d_j)$ 的最大值只在 $j < i$ 的时候取到，那么我们找到 $s_i + d_i$ 的最大值 $s_p + d_p$ 且 $p$ 最大（ $p$ 必须最大），那么 $-s_j + d_j$ 的最大值只能在 $j \le p$ 取到，而 $j = p$ 显然不合法，所以我们找 $j < p$ 时 $-s_j + d_j$ 的最大值即可。
由于 $(s_i + d_i) + (-s_j + d_j)$ 的最值只在 $j < i$ 的时候取到，而我们的 $p$ 又是最大的，所以充分性是显然的。
又由于区间后移的过程中 $p$ 只增不减，所以只需两个单调队列分别维护两个括号内的最值即可，复杂度 $O(n)$ 。
问题完美解决！

代码

//  Created by Sengxian on 5/20/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3242 NOI 2013 D2T2 基环树
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 1000000 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
struct edge {
    int from, to, cost;
    edge(int from, int to, int cost): from(from), to(to), cost(cost) {}
    inline int To(int u) const {
        if (u == from) return to;
        else return from;
    }
};
vector<edge> edges;
vector<int> G[maxn];
int n, in[maxn], pre[maxn];
ll d[maxn], s[maxn], tree_ans = 0;

void toposort() {
    queue<int> q;
    for (int i = 0; i < n; ++i)
        if (in[i] == 1) d[i] = 0, q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < (int)G[u].size(); ++i) {
            const edge &e = edges[G[u][i]];
            int v = e.To(u);
            if (in[v] > 1) {
                tree_ans = max(tree_ans, d[v] + d[u] + e.cost);
                d[v] = max(d[v], d[u] + e.cost);
                if (--in[v] == 1) q.push(v);
            }
        }
    }
}

vector<int> cir;

void getCir(int x) {
    queue<int> q;
    q.push(x);
    pre[x] = -1, s[x] = 0;
    bool flag = false;
    cir.clear();
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == x) { //再走一次第一个，目的是获取整个环的长度
            if (flag == false) flag = true;
            else break;
        }
        cir.push_back(u);
        for (int i = 0, v = 0; i < (int)G[u].size(); ++i) {
            v = edges[G[u][i]].To(u);
            if (G[u][i] != pre[u] && in[v] > 1) {
                s[v] = s[u] + edges[G[u][i]].cost;
                pre[v] = G[u][i];
                q.push(v);
                break;
            }
        }
    }
}


ll v1[maxn * 2], v2[maxn * 2];
int q1[maxn], q2[maxn];

ll getAns(int x) {
    getCir(x);
    int k = cir.size();
    ll Max = 0, ans = INF, allLength = s[cir[0]];
    s[cir[0]] = 0;
    for (int i = 0; i < k; ++i) {
        v1[i] = s[cir[i]] + d[cir[i]];
        v2[i] = -s[cir[i]] + d[cir[i]];
    }
    for (int i = 0; i < k; ++i) {
        v1[i + k] = (s[cir[i]] + allLength) + d[cir[i]];
        v2[i + k] = -(s[cir[i]] + allLength) + d[cir[i]];
    }

    int l1 = 0, r1 = 0, l2 = 0, r2 = 0, last = -1;
    for (int i = 0; i < k; ++i) {        
        while (r1 - l1 >= 1 && v1[i] >= v1[q1[r1 - 1]]) r1--;
        q1[r1++] = i;
    }
    for (int i = 0; i < q1[l1]; ++i) {
        while (r2 - l2 >= 1 && v2[i] >= v2[q2[r2 - 1]]) r2--;
        q2[r2++] = i;
    }
    last = q1[l1];
    ans = v1[q1[l1]] + v2[q2[l2]];
    for (int i = 1; i < k; ++i) {
        while (r1 - l1 >= 1 && q1[l1] < i) l1++;
        while (r2 - l2 >= 1 && q2[l2] < i) l2++;
        while (r1 - l1 >= 1 && v1[i + k - 1] >= v1[q1[r1 - 1]]) r1--;
        q1[r1++] = i + k - 1;
        for (int j = last; j < q1[l1]; ++j) {
            while (r2 - l2 >= 1 && v2[j] >= v2[q2[r2 - 1]]) r2--;
            q2[r2++] = j;
        }
        last = q1[l1];
        ans = min(ans, v1[q1[l1]] + v2[q2[l2]]);
    }
    return ans;
}

int main() {
    n = ReadInt();
    for (int i = 0; i < n; ++i) {
        int u = ReadInt() - 1, v = ReadInt() - 1;
        edges.push_back(edge(u, v, ReadInt()));
        G[u].push_back(edges.size() - 1);
        G[v].push_back(edges.size() - 1);
        in[u]++, in[v]++;
    }
    ll ans = 0;
    toposort();
    for (int i = 0; i < n; ++i) if (in[i] > 1) {ans = getAns(i); break;}
    printf("%.1lf\n", max(tree_ans, ans) / 2.0);
    return 0;
}

BZOJ 2323 - [ZJOI2011]细胞 BZOJ 3244 - [Noi2013]树的计数

Sengxian's Blog

BZOJ 3242 - [Noi2013]快餐店

描述

分析

代码