欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POI2014 RAJ-Rally

程序员文章站 2022-07-13 12:34:56
...

Description

给定一个\(N\)个点\(M\)条边的\(DAG(N,M\leq10^6)\),边权为\(1\)。删去一个点,使剩余图中的最长路径最短,求删去的点和最长路径长度。

Solution

神仙而有趣的一题\(Orz\),可能讲的不是很清楚\(QAQ\)

先求出终点为\(u\)的最长路\(f_u\)和起点为\(u\)的最长路\(g_u\),经过\((u,v)\)边的最长路为\(f_u+g_v+1\),这个可以用建正反图然后拓扑排序得到。

考虑删除\(u\)点,即不经过\(u\)的入边与出边的最长路,暴力就是把所有最长路权值丢到数据结构中,然后每次删除一些权值后统计答案,复杂度\(O(n^2logn)\),难以接受。

考虑\(DAG\)的性质,每一条边\((u->v)\)\(u\)的拓扑序小于\(v\)。所以考虑按拓扑序处理,处理\(u\)前,把反图的出边相关信息\(pop\),统计答案后把正图的出边相关信息\(push\)

然后我们需要一个支持\(pop,push\)指定数并求出\(max\)的数据结构,用两个堆(优先队列)就可以做到了。

Code

#include<cstdio>
#include<vector>
#include<queue>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=500005;
vector<int> G[N], IG[N];
struct Priority_queue
{
    priority_queue<int> a, b;
    void push(int x){a.push(x);}
    void pop(int x){b.push(x);}
    int top()
    {
        while (!b.empty() && a.top()==b.top()) 
            a.pop(), b.pop(); 
        return a.top();
    }
}Q;
int deg[N], q[N], f[N], g[N], l, r, ans, pos;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

int main()
{
    int n=read(), m=read(); ans=m;
    rep(i, 1, m) 
    {
        int u=read(), v=read();
        G[u].push_back(v); IG[v].push_back(u);
        deg[v]++;
    }
    rep(i, 1, n) if (!deg[i]) q[++r]=i;
    while (l<r)
    {
        int u=q[++l]; 
        for (int v: G[u]) if (!(--deg[v])) q[++r]=v;
    }
    rep(i, 1, n)
    {
        int u=q[i];
        for (int v: G[u]) f[v]=max(f[v], f[u]+1);
    }
    per(i, n, 1)
    {
        int u=q[i];
        for (int v: IG[u]) g[v]=max(g[v], g[u]+1);
    }
    rep(i, 1, n) Q.push(g[i]), Q.push(-1);
    rep(i, 1, n)
    {
        int u=q[i]; 
        for (int v: IG[u]) Q.pop(f[v]+g[u]+1);
        Q.pop(g[u]);
        if (ans>Q.top()) ans=Q.top(), pos=u;
        for (int v: G[u]) Q.push(f[u]+g[v]+1);
        Q.push(f[u]);
    }
    printf("%d %d\n", pos, ans);
    return 0;
}