bzoj3832

拓扑排序+set

如果我们直接记录所有路径是不行的，那么我们要降低路径的数量，于是我们把最短路径转换到边上，这样我们就只有m条路径了。

先计算出f[i]和g[i]表示正反拓扑最长链，把所有g插到set里，然后按照拓扑序依次枚举删点，把之前加入过的边删除，删除g[u]，查询最大值，然后加入后继边每条边的权值就是f[x]+g[to]+1，再加入f[u]这样我们按照拓扑序就不用加入之前删掉的边，因为我们是按照拓扑序删的，这样后面删的点肯定会影响之前的最长链，如果不影响则说明最长链已经被枚举完了，所以之前的最长链自然也受影响。

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5 + ;

int n, m, tot, ans = 0x3f3f3f3f, p;

vector<int> G[N], rev[N];

int in[N], a[N], f[N], g[N];

int rd()

{

    int x = , f = ; char c = getchar();

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

    while(c >= '' && c <= '') { x = x *  + c - ''; c = getchar(); }

    return x * f;

}

multiset<int> s;

int main()

{

    n = rd();

    m = rd();

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

    {

        int u = rd(), v = rd();

        G[u].push_back(v);

        rev[v].push_back(u);

        ++in[v];

    }

    queue<int> q;

    for(int i = ; i <= n; ++i) if(in[i] == ) q.push(i);

    while(!q.empty())

    {

        int u = q.front();

        a[++tot] = u;

        q.pop();

        for(int i = ; i < G[u].size(); ++i)

        {

            int v = G[u][i];

            f[v] = max(f[v], f[u] + );

            if(--in[v] == ) q.push(v);

        }

    }

    for(int i = n; i; --i)

    {

        int u = a[i];

        for(int j = ; j < rev[u].size(); ++j)

        {

            int v = rev[u][j];

            g[v] = max(g[v], g[u] + );

        }

    }

    for(int i = ; i <= n; ++i) s.insert(g[i]);

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

    {

        int u = a[i];

        multiset<int> :: iterator it;

        it = s.find(g[u]);

        if(it != s.end()) s.erase(it);

        for(int j = ; j < rev[u].size(); ++j)

        {

            it = s.find(f[rev[u][j]] + g[u] + );

            s.erase(it);

        }

        if(!s.empty()) if(*(s.rbegin()) < ans) ans = *(s.rbegin()), p = u;

        for(int j = ; j < G[u].size(); ++j)

            s.insert(g[G[u][j]] + f[u] + );

        s.insert(f[u]);

    }

    printf("%d %d\n", p, ans);

    return ;

}

巴特西

bzoj3832

最新文章

热门文章