PO2014 Rally

Rally

POI2014

题意

1.有一个N个点M条边的有向无环图，每条边长度都是1

2.找到一个点，使得删掉这个点后剩余的图中的最长路径最短

3.问删去的点哪个点，以及删掉这个点后剩余的图中的最长路径长度为多少

解

1.存下每个点的入边，出边(分开存)

2.预处理每个点沿着出边最长链是多少(dis2[x])，沿着入边走最长链是多少(dis1[x])

3.先把所有点出边最长链(dis2[x])放进multiset(到时候要查询最大最小值)

4.按照入度拓扑排序，依次遍历每个点

5.遍历到x点时
先把能够进入它的点(y)与它(x)组成的最长链都删去
y->x 删去dis1[y]+1+dis2[x]
再删去x点的出边最长链
删去dis2[x]

6.此时multiset中的最大值就是删去x点后的最长链长度

7.把能够从它连出去的点(y)与(x)组成的最长链都加入
x->y 加入dis2[y]+1+dis1[x]
把x点的入边最长链加入
加入dis1[x]

具体代码

#include<bits/stdc++.h>
using namespace std;
const int M=500005;
int n,m,rdu[M],cdu[M],du[M];
int head[M],asdf,rhead[M],rasdf;
multiset<int>S;
multiset<int>::iterator it;
struct edge {
    int to,nxt;
} G[M*2],rG[M*2];
void add_edge(int a,int b) {
    G[++asdf].to=b;
    G[asdf].nxt=head[a];
    head[a]=asdf;
    rG[++rasdf].to=a;
    rG[rasdf].nxt=rhead[b];
    rhead[b]=rasdf;
}
int dis1[M],dis2[M],q[M],l,r;
void init() {
    l=r=1;
    for(int i=1; i<=n; i++) {
        if(!rdu[i])q[r++]=i;
    }
    while(l<r) {
        int x=q[l++];
        for(int i=head[x]; i; i=G[i].nxt) {
            int y=G[i].to;
            if(!(--rdu[y]))q[r++]=y;
            dis1[y]=max(dis1[y],dis1[x]+1);
        }
    }
    l=r=1;
    for(int i=1; i<=n; i++) {
        if(!cdu[i])q[r++]=i;
    }
    while(l<r) {
        int x=q[l++];
        for(int i=rhead[x]; i; i=rG[i].nxt) {
            int y=rG[i].to;
            if(!(--cdu[y]))q[r++]=y;
            dis2[y]=max(dis2[y],dis2[x]+1);
        }
    }
}
void solve() {
    int ans=1e9,px=0;
    l=r=1;
    for(int i=1; i<=n; i++) {
        if(!du[i])q[r++]=i;
        S.insert(dis2[i]);
    }
    while(l<r) {
        int x=q[l++];
        for(int i=rhead[x]; i; i=rG[i].nxt) {
            int y=rG[i].to;
            it=S.find(dis1[y]+1+dis2[x]);
            if(it!=S.end())S.erase(it);
        }
        it=S.find(dis2[x]);
        if(it!=S.end())S.erase(it);
        if(S.size()) {
            it=S.end();
            it--;
            if((*it)<ans) {
                ans=*it;
                px=x;
            }
        }
        S.insert(dis1[x]);
        for(int i=head[x]; i; i=G[i].nxt) {
            int y=G[i].to;
            if(!(--du[y]))q[r++]=y;
            S.insert(dis2[y]+1+dis1[x]);
        }
    }
    printf("%d %d\n",px,ans);
}
int main() {
    int a,b;
    scanf("%d %d",&n,&m);
    for(int i=1; i<=m; i++) {
        scanf("%d %d",&a,&b);
        add_edge(a,b);
        rdu[b]++,cdu[a]++;
        du[b]++;
    }
    init();
    solve();
    return 0;
}