Luogu 1399 [NOI 2013] 快餐店

2023-05-16

- - - - 传送门
      - 思路
      - 参考代码
      - Remarks
      - 总结

传送门

思路

发现这是一棵环套树。那首先我们会想到树上的情况。如果这是一棵树，我们自然会联想到树的直径，自然会想到对于树而言，答案为直径长度的一半。

证明
用反证法。假设直径的中点不是最佳选址，那么必然存在一条从该点出发的路径使得长度超过直径的一半。但这就说明存在一条比直径更长的路径，与直径的定义矛盾。
证毕。

回到环套树上，我们把这个环套树看成多棵树的根被串成一个环。首先，如果最终答案的快餐店建立在树中，那么最远的路径一定是所在树的直径，这个可以直接 DP。如果最终答案的快餐店建立在环上，那么从它出发到其它点一定会有一条环上的边不会被经过（因为都往近的走，那么就一定有个分界线）当然，就算快餐店在树中，也总有一条环上的边不会被经过，理由相同。

我们发现，最终答案一定能找到两个点，使得这两点到快餐店的距离相等且最远。如果只保证了最远而不保证相等，那么我们可以把快餐店向远的那个点移动，答案会变小。我们称这两个点为两个端点。

现在我们不知道答案的快餐店在哪儿，我们先假设两个端点都在同一棵树中。发现，如果事实并不是这样，那么正确答案一定比假设端点在同一棵树中的答案大（有一条更长的路）。如果我们假设两个端点在不同树中，而事实并不是这样的话，正确答案也一定比假设端点在不同树中的答案大。因此我们做两次假设，然后取最大值就好了。如果两个端点在同一棵树中，就是所有树的直径的最大值。接下来我们只考虑两个端点在不同树中的情况。

于是我们立即得到一个 $O(n^2)$ 的算法：枚举最终答案不经过环上的哪条边，则我们剩下了一棵树，用 $O(n)$ 的时间复杂度求树的直径。我们取它们的最小值，即为答案。为什么取最小值呢？因为最终答案一定有一条在环上不被经过的边，此时所有路径都是最优的。现在我们保留那条不走的边，删去另外一条环上的边，则原来一些最优的路线会绕路，答案就会变劣。因此最小值就是最后的答案。

这个做法显然不够，我们考虑数学化一点。现在我们可以直接把这个环套树抽象成：

即把所有树抽象成一条边，边权为这棵树过根结点的最长的祖先后代链。

我们现在的任务是：枚举环上被删除的边，然后求最长链，最后对它们求最小值。

设树抽象成的边的边权为 $d$ 。那么答案就是：

max {d_{i} + d_{j} + d i s t (i, j)}

$\max \{ d_i + d_j + dist(i, j) \}$
其中 i i $i$ 和

j

$j$ 表示环上的两点， dist(i,j) d i s t ( i , j ) $dist(i, j)$ 表示 i i $i$ 到

j

$j$ 在枚举的边被删去时的距离。

考虑把环拆开，让环变成线性结构，这样我们就可以用前缀和来表示 $dist$ 。为了方便地涵盖所有情况，我们可以把环拆成链后复制一遍放在后面，得到一条长度为 $2l$ 的链（设环的长度为 $l$ ），然后依次考虑其中连续的长度为 $l$ 的区间，这就相当于是在枚举断哪条边。

不妨设 $i > j$ ，那么我们要求的是：

max{di+dj+si−sj} max { d i + d j + s i − s j }

$\max \{ d_i + d_j + s_i - s_j \}$

其中 $s$ 表示环上距离的前缀和。

分组：

max {(d_{i} + s_{i}) + (d_{j} - s_{j})}

$\max \{ (d_i + s_i) + (d_j - s_j) \}$

我们用可重集维护前后的最大值和次大值，然后就能查询了。

但是如何保证 $i > j$ 呢？显然，如果 $i > j$ ，那么 $d_i + d_j + s_i - s_j > d_i + d_j + s_j - s_i$ ，由于我们取 $\max$ ，因此自然就保证了 $i > j$ 。这也是非法解不会最优的例子。

对于所有 $l$ 个查询结果，我们取一个最小值，代表假设答案经过环时的长度。再与假设答案是树的直径的长度取最大值即可。

时间复杂度 $O(n \log n)$ 。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int maxn = int(1e5) + 5;
int n;
struct Graph
{
    struct Edge
    {
        int to;
        int cost;
        int next;
    } edges[maxn * 2];
    int head[maxn];
    int i;
    Graph() : i() { memset(head, -1, sizeof(head)); }
    void addEdge(int from, int to, int cost)
    {
        edges[i].to = to;
        edges[i].cost = cost;
        edges[i].next = head[from];
        head[from] = i;
        i++;
    }
#define idx(G) idx_##G
#define wander(G, node) for (int idx(G) = G.head[node]; ~idx(G); idx(G) = G.edges[idx(G)].next)
#define DEF(G) const Graph::Edge& e = G.edges[idx(G)]; int to = e.to; int cost = e.cost
} G;

#define RunInstance(x) delete new x
struct brute
{
    bool vis[maxn];
    std::vector<int> onRing;
    int tag;

    bool DFS1(int node, int parent)
    {
        vis[node] = true;
        wander(G, node)
        {
            DEF(G);
            if (to == parent) continue;
            if (vis[to])
            {
                tag = to;
                onRing.push_back(idx(G) >> 1);
                return true;
            }
            if (DFS1(to, node) && tag != to)
            {
                onRing.push_back(idx(G) >> 1);
                return true;
            }
        }
        return false;
    }

    LL d;
    LL f[maxn];
    void DFS2(int node, int parent)
    {
        LL major = 0, minor = 0;
        wander(G, node)
        {
            if ((idx(G) >> 1) == tag) continue;
            DEF(G);
            if (to == parent) continue;
            DFS2(to, node);
            f[node] = std::max(f[node], f[to] + cost);
            if (f[to] + cost > minor)
                if (f[to] + cost > major)
                {
                    minor = major;
                    major = f[to] + cost;
                }
                else
                    minor = f[to] + cost;
        }
        d = std::max(d, major + minor);
    }

    brute() : vis()
    {
        DFS1(1, 0);

        LL ans = LLONG_MAX;
        for (int i = 0; i < onRing.size(); i++)
        {
            tag = onRing[i];
            memset(f, 0, sizeof(LL) * (n + 1));
            d = 0;
            DFS2(1, 0);
            ans = std::min(ans, d);
        }
        printf("%.1f", (double)ans / 2);
    }
};
LL f[maxn];
int vs[maxn * 2];
LL cost[maxn * 2];
struct work
{
    bool vis[maxn];
    std::vector<int> onRing;
    std::vector<int> vertex;
    std::vector<int> dis;
    int tag;

    bool DFS1(int node, int parent)
    {
        vis[node] = true;
        wander(G, node)
        {
            DEF(G);
            if (to == parent) continue;
            if (vis[to])
            {
                tag = to;
                onRing.push_back(idx(G) >> 1);
                vertex.push_back(to);
                dis.push_back(cost);
                return true;
            }
            if (DFS1(to, node) && tag != to)
            {
                onRing.push_back(idx(G) >> 1);
                vertex.push_back(to);
                dis.push_back(cost);
                return true;
            }
        }
        return false;
    }

    LL D[maxn];
    void DFS2(int node, int parent)
    {
        LL major = 0, minor = 0;
        D[node] = 0;
        f[node] = 0;
        wander(G, node)
        {
            DEF(G);
            if (vis[to] || to == parent) continue;
            DFS2(to, node);
            f[node] = std::max(f[node], f[to] + cost);
            D[node] = std::max(D[node], D[to]);

            if (f[to] + cost > minor)
                if (f[to] + cost > major)
                {
                    minor = major;
                    major = f[to] + cost;
                }
                else
                    minor = f[to] + cost;
            D[node] = std::max(D[node], major + minor);
        }
    }

    int l;

    struct Comp1
    {
        bool operator()(const int& a, const int& b) const
        {
            return f[vs[a]] + cost[a] > f[vs[b]] + cost[b];
        }
    };
    struct Comp2
    {
        bool operator()(const int& a, const int& b) const
        {
            return f[vs[a]] - cost[a] > f[vs[b]] - cost[b];
        }
    };

    work() : vis()
    {
        DFS1(1, 0);
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < vertex.size(); i++)
            vis[vertex[i]] = true;
        for (int i = 0; i < vertex.size(); i++)
        {
            int v = vertex[i];
            DFS2(v, 0);
        }
        l = vertex.size();
        for (int i = 0; i < l; i++)
        {
            vs[i + 1] = vertex[i];
            cost[i + 2] = dis[i];
        }
        for (int i = l + 1; i <= (l << 1); i++)
        {
            vs[i] = vs[i - l];
            cost[i + 1] = cost[i + 1 - l];
        }

        for (int i = 2; i <= (l << 1) + 1; i++)
            cost[i] += cost[i - 1];
        std::multiset<int, Comp1> set1;
        std::multiset<int, Comp2> set2;

        for (int i = 1; i <= l; i++)
        {
            set1.insert(i);
            set2.insert(i);
        }
        LL ans = LLONG_MAX;
        for (int i = l + 1; i <= (l << 1); i++)
        {
            auto it11 = set1.begin();
            auto it12 = it11; it12++;
            auto it21 = set2.begin();
            auto it22 = it21; it22++;
            if (*it11 != *it21)
                ans = std::min(ans, f[vs[*it11]] + f[vs[*it21]] + cost[*it11] - cost[*it21]);
            else
            {
                ans = std::min(ans,
                    std::max(f[vs[*it12]] + f[vs[*it21]] + cost[*it12] - cost[*it21],
                        f[vs[*it11]] + f[vs[*it22]] + cost[*it11] - cost[*it22]));
            }

            set1.erase(set1.find(i - l)); // note: find!!!
            set2.erase(set2.find(i - l));
            set1.insert(i);
            set2.insert(i);
        }

        for (int i = 0; i < vertex.size(); i++)
            ans = std::max(ans, D[vertex[i]]);
        printf("%.1f", (double)ans / 2);
    }
};

void run()
{
    n = readIn();
    for (int i = 1; i <= n; i++)
    {
        int from = readIn();
        int to = readIn();
        int cost = readIn();
        G.addEdge(from, to, cost);
        G.addEdge(to, from, cost);
    }

    RunInstance(work);
}

int main()
{
    run();
    return 0;
}

Remarks

我们要取一个滑动窗口内的最大值，这个可以用单调队列，时间复杂度为 $O(n)$ 。（没试过，不过不是还要求次大值吗？？？）

总结

为什么我卡了一天？因为我没有注意到最重要的一点是最终答案一定有一条在环上的边不会经过。唉，我太弱啦！没学上啦！滚粗啦！唉，我太弱啦！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)