• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

P3573 [POI2014]RAJ-Rally

admin

11月 28, 2021

Problem

给一个(n)个点,(m)条边的DAG,找到一个点,使得删去这个点后的最长路径最短。
(2 le n le 500000,1 le m le 1000000)

Solution

看到DAG就想到拓扑。
求出以(x)为起点的最长路径长度(ds_x)和以(x)为终点的最长路径长度(dt_x)。可以通过跑正反图拓扑实现。
设第(x)个点的拓扑序为(TX_x)
对于一条边(u o v),经过它的最长路径长度为(dt_u + ds_v + 1),正确性显然。
考虑枚举删的点,假设我们现在删除(x),我们假设所有(TX_i < TX_x)的点放在集合(A)(TX_i > TX_x)的放在集合(B)(x)在中间。
此时的最长路径分三种:(A o A,A o B,B o B)

  • (A o A)(max_{i in A} {dt_i})
  • (A o B)(max_{(u,v) in E,u in A,v in B} {dt_u +ds_v + 1 })
  • (B o B)(max_{i in B} {ds_i})

(x)原来在(B)集合,现在不在(B)集合,则删除(ds_x)
(x)在反图中连接的点都存在第二种情况,删除。

下一次删除前,(x)(A)集合,则加入(dt_x)
(x)在图中连接的点都存在第二种情况,加入。

发现需要维护一个支持删除加入,求最值的东西,那么可以使用平衡树权值线段树。(其实multiset应该可以,但是我不会用)

# include<bits/stdc++.h>
using namespace std;
const int N = 500005,M = 1000005;
int n,m;
vector <int> g[N],g2[N];
int ds[N],dt[N];
int du[N],du2[N];
int Tx[N],Txtot = 0;
int q[N];
void topsort(void) //dt
{
    queue <int> q;
    for(int i = 1; i <= n; i++)
    {
        if(du[i] == 0)
        {
            q.push(i);
            Tx[i] = ++Txtot;
        }
    }
    while(!q.empty())
    {
        int x = q.front(); q.pop();
        for(int i = 0; i < (int)g[x].size(); i++)
        {
            int v = g[x][i];
            dt[v] = max(dt[v],dt[x] + 1);
            if(--du[v] == 0) q.push(v),Tx[v] = ++Txtot;
        }
    }
    return;
}
void topsort2(void)
{
    queue <int> q;
    for(int i = 1; i <= n; i++)
    {
        if(du2[i] == 0)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int x = q.front(); q.pop();
        for(int i = 0; i < g2[x].size(); i++)
        {
            int v = g2[x][i];
            ds[v] = max(ds[v],ds[x] + 1);
            if(--du2[v] == 0) q.push(v);
        }
    }
    return;
}
bool compare(const int &x,const int &y)
{
    return Tx[x] < Tx[y];
}
struct node
{
    int val,l,r;
}T[N << 2];
int tot = 1;
void build(int root,int l,int r)
{
    if(l == r) {T[root].val = 0,T[root].l = T[root].r = 0; return;}
    int mid = (l + r) >> 1;
    T[root].l = ++tot,T[root].r = ++tot;
    build(T[root].l,l,mid),build(T[root].r,mid + 1,r);
    return;
}
void update(int root,int l,int r,int x,int d)
{
    if(l == r && l == x)
    {
        T[root].val += d;
        return;
    }
    int mid = (l + r) >> 1;
    if(l <= x && x <= mid) update(T[root].l,l,mid,x,d);
    else if(x > mid) update(T[root].r,mid + 1,r,x,d);
    T[root].val = T[T[root].l].val + T[T[root].r].val;
    return;
}
int query(int root,int l,int r)
{
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(T[T[root].r].val > 0) return query(T[root].r,mid + 1,r);
    else return query(T[root].l,l,mid);
}
int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++)
    {
        int a,b; scanf("%d%d",&a,&b);
        g[a].push_back(b),g2[b].push_back(a);
        ++du[b],++du2[a];
    }
    topsort(),topsort2();
    build(1,1,2 * n);
    for(int i = 1; i <= n; i++)
    {
        update(1,1,2 * n,ds[i],1); q[i] = i;
    }
    sort(q + 1, q + n + 1, compare);
    int ans = 1e9 + 7,id = 0;
    for(int i = 1; i <= n; i++) // delete i
    {
        update(1,1,2 * n,ds[q[i]],-1);
        for(int j = 0; j < (int)g2[q[i]].size(); j++)
        {
            int v = g2[q[i]][j];
            update(1,1,2 * n,dt[v] + 1 + ds[q[i]],-1);
        }
        // printf("i = %d,max = %d
",i,Max);
        int Max = query(1,1,2 * n);
        // printf("i = %d,Max = %d
",i,Max);
        if(Max < ans) 
        {
            ans = Max,id = q[i];
        }
        // S.insert(dt[i]);
        update(1,1,2 * n,dt[q[i]],1);
        for(int j = 0; j < (int)g[q[i]].size(); j++)
        {
            int v = g[q[i]][j];
            update(1,1,2 * n,dt[q[i]] + 1 + ds[v],1);
        }
    }
    printf("%d %d
",id,ans);
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。