题解：P8860 动态图连通性

· · 题解

文章将同步在博客园发表。

题面

转化题。

首先显然无法在线做，不然就真的成动态图连通性了。

我们假设第 i 条边被删除的时间是 d_i（如果没被删那就设为 \infty），那么题目实际上就是让我们找到一条从 1 到 n 的路径，使得：

  1. 路径上最小的 d 尽可能大。

  2. 在满足条件一的情况下，路径上第二小的 d 尽可能大。

  3. 在满足条件一、二的情况下，路径上第三小的 d 尽可能大。

依次类推。

其实就是把路径上的 d 从小到大排序，然后取字典序最大的那个，别的路都可以删。

现在的问题就是如何找到这条路。

在这之前我们先考虑一下别的情况：

如果同一条边被删除了多次，那么显然我们以第一次删除的时间为准，后面的删除操作的答案显然都是 0，直接标记就行了。

回到找路径这里。因为每个 d 只会出现一次，所以我们可以考虑把所有的 d 刻画到某个东西上面然后用最短路（或最长路）做。

显然我可以把 d_i 视作 10^{d_i}，此时我如果经过了这条边，那么我就对距离做 10^{d_i} 的贡献，但是这样如果我们要比较两条路径的长度，就需要从最低位开始比，因此我们可以反过来用 10^{q-d_i}。

此时上面的条件就被我们转化为最短路问题。我们考虑怎么做这个最短路问题。

显然你如果加一个 10^{q-d_i}，就相当于把 q-d_i 这个位置从 0 变成 1，因此我们可以用可持久化线段树来维护每一位，比较就用字典序比较就行。显然这是可以实现的。

但是可持久化线段树实现稍微有点复杂，所以我们来观察性质。

我们考虑两个点 st_1 和 st_2，如果它们都能转移给点 ed，那么会出现什么性质。

现在我们考虑 q-d_2：如果 q-d_2\ge q-d_1，此时 d_1\ge d_2，那么显然 dis_{st_2}+10^{q-d_2}>dis_{st_1}+10^{q-d_1}，否则 dis_{st_2}+10^{q-d_2}<dis_{st_1}+10^{q-d_1}。进一步观察我们会发现：这实际上就是取所有能转移的当中 d 最大的来转移。

因此我们直接将第一维改为 d，并按照 d 从大到小排序。

代码：

const int N=2e5+6;
struct edge{
    int x,y;
}e[N];
int n,m,q,d[N],la[N];
bool ans[N],vis[N];
vector<int>v[N];
signed main()
{
    n=read(),m=read(),q=read();
    for(int i=1,x,y;i<=m;i++)
    {
        x=read(),y=read();
        e[i]=(edge){x,y};
        v[x].push_back(i);
        d[i]=q+1;
    }
    for(int i=1;i<=q;i++)
    {
        int x=read();
        if(d[x]>q)
        {
            d[x]=i;
            ans[i]=true;
        }
        else
        {
            ans[i]=false;
        }
    }
    priority_queue<pair<int,int>>pq;
    pq.push(make_pair(0,m+1));
    e[m+1].y=1;
    while(!pq.empty())
    {
        pair<int,int>p=pq.top();
        pq.pop();
        int x=e[p.second].y;
        if(vis[x])
        {
            continue;
        }
        vis[x]=1;
        la[x]=p.second;
        for(auto i:v[x])
        {
            pq.push(make_pair(d[i],i));
        }
    }
    for(int i=n;i;i=e[la[i]].x)
    {
        ans[d[la[i]]]=false;
    }
    for(int i=1;i<=q;i++)
    {
        write(ans[i]?1:0);
        putchar('\n');
    }
    return 0;
}