BZOJ 3832 - [Poi2014]Rally | Sengxian's Blog

BZOJ 3832 - [Poi2014]Rally

#堆 #拓扑排序

Published on 2016-06-26

描述

给定一个 $n(n\le 500000)$ 个点 $m(m\le 1000000)$ 条边的有向无环图，每条边长度都是 $1$ ，请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。

分析

这个题目如果直接思考的话，最棘手的就是如何处理删去一个点的影响，这个是很难直接办到的，然后就不会做了。
神题有神解法啊。

新建源汇 $s, t$ ，源点连向所有点，所有点连向汇点。则我们将图的最长链转化为 $s\rightarrow t$ 的最长链，这是个常用技巧。
根据拓扑序的性质，只有拓扑序小的点向拓扑序大的点连边，所以我们直接用拓扑序求出 $g_i$ 表示 $s\rightarrow i$ 的最长链，再反着来一次，求出 $f_i$ 表示 $i \rightarrow t$ 的最长链。则对于一条边 $u\rightarrow v$ 来说，它的最优答案是 $g_u + f_v - 1$ 。
则最长链变为所有边的最优答案。

我们求出 $s\rightarrow t$ 的一个割（不一定是最小割啊，不要网络流做多），那么所有路径必然经过割集中的边！也就是，我们只用知道“任意一个割”中的所有边的最优答案即可。
我们枚举每个点，如果能知道去掉这个点之后，图的一个割，那我们就能知道去掉这个点之后图的最长链！
不妨一开始让令初始 $s$ 集只有 $s$ ，所有点和 $t$ 都在 $t$ 集，相当于割去了所有 $s\rightarrow u$ 的边，这是一个可行的割。
我们按照拓扑序，依次将点从 $t$ 集中拿掉，给到 $s$ 集，如下操作：

将这个点的所有入边从割集中删掉。
割集的边的最优答案最大值就是删掉这个点的答案。
将这个点的所有出边加入割集中。

可用归纳法证明正确性，执行第一步之前，图是一个完整的割，这个割不含 $u$ 出发能到的任何边，删掉 $u$ 的所有入边之后，自然是图中删除掉 $u$ 的一个割，而根据拓扑序，如果一条边能到 $u$ ，那么它不可能在割集中，所以此时割集的边的最优答案最大值就是删掉这个点的答案。
接着将这个点放回图，可行的路径只有形如 $s\rightarrow u \rightarrow t$ 的路径，去掉 $u$ 的所有出边，自然又形成了图的一个割。

割集可以用一个堆维护，而带删除的堆，可用两个堆来维护。
复杂度 $O(m\log m)$ 。

总结：

代码

//  Created by Sengxian on 6/26/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3832 拓扑排序 + 堆
#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;
}

namespace Heap {
    priority_queue<int> q1, q2;
    inline void insert(int v) {q1.push(v);}
    inline void erase(int v) {q2.push(v);}
    inline int top() {
        while (q1.size() && q2.size() && q1.top() == q2.top()) q1.pop(), q2.pop();
        return q1.top();
    }
}

const int maxn = 500000 + 3;
vector<int> G[maxn], rG[maxn], topo;
int n, m, in[maxn], g[maxn], f[maxn];

void topo_sort() {
    queue<int> q;
    for (int i = 0; i < n; ++i) if (!in[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (--in[v] == 0) q.push(v);
        }
    }
}

int main() {
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < m; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        G[f].push_back(t), in[t]++;
        rG[t].push_back(f);
    }
    topo_sort();
    for (int i = 0; i < n; ++i) {
        int u = topo[i];
        g[u] = max(g[u], 1);
        for (int j = 0; j < (int)G[u].size(); ++j) {
            int v = G[u][j];
            g[v] = max(g[v], g[u] + 1);    
        }
    }
    for (int i = n - 1; ~i; --i) {
        int u = topo[i];
        f[u] = max(f[u], 1);
        for (int j = 0; j < (int)G[u].size(); ++j) {
            int v = G[u][j];
            f[u] = max(f[u], f[v] + 1);    
        }
    }
    for (int i = 0; i < n; ++i) Heap::insert(f[i]); //s -> i 的边加入割集
    Heap::insert(0); //防止堆空
    int mn = INT_MAX, id = -1;
    for (int x = 0; x < n; ++x) {
        int u = topo[x];
        //到这里保证是一个割，且不含任何 u 能到达的边
        for (int i = 0; i < rG[u].size(); ++i) //删除所有到 u 的边
            Heap::erase(g[rG[u][i]] + f[u]);
        Heap::erase(f[u]); //删除 s -> u 的边
        //现在还是一个割，但是所有的边均与 u 无关
        if (Heap::top() < mn) mn = Heap::top(), id = u;
        for (int i = 0; i < G[u].size(); ++i) //加入从 u 出发的边，由于没有到 s -> u 的路径，所以仍然是割。
            Heap::insert(g[u] + f[G[u][i]]);
        Heap::insert(g[u]);
    }
    printf("%d %d\n", id + 1, mn - 1);
    return 0;
}

BZOJ 3754 - Tree之最小方差树 Codeforces 682D - Alyona and Strings