P8860 动态图连通性

简单巧妙的一题。

首先注意到，一条边只有第一次被考虑时有意义，如果被删了，那么之后都不会被删；如果没删，那么它一定是 $1\to n$ 的必经边，之后也不会被删。于是我们考虑求出每条边被删的时间，没被删的边的时间就是 $q+1$。

我们相当于要求出一条最终被留下的路径。我们先处理出每条边若果不是最终边的话，被删去的时间 $t_i$。那么我们要求一条满足路径上的边中最小的 $t_i$ 尽可能大的路径，更多地，我们需要保证次小的 $t_i$ 也尽可能大。换言之，我们需要求出一条路径，满足路径上的边的 $t_i$ 排序之后，满足字典序最大。

我们仔细思考如何对这样的路径进行扩展。一个贪心的想法是我们每次都尝试向 $t_i$ 更大的边走。但发现这样很对，因为一条 $t_i$ 较小的边 $i$ 只会在 $t_j>t_i$ 的边 $i$ 被扩展完了之后，才会扩展 $i$，此时必经边 $x$ 满足 $t_x\le t_i$，而同时我们保证了前面较大边的最大性。所以一直这样做下去，最终得到的最优路径就是我们所求的。

经过上面的分析，我们只需要用一个 Dijkstra 并且在过程中记录前驱。时间复杂度 $\mathcal O(n\log n)$。

Code

#include<iostream>
#include<cstdio>
#include<queue>
#define fi first
#define se second
using namespace std;
using PII=pair<int,int>;
const int N=2e5+10,M=2e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,q;
int u[M],v[M],a[M];
bool ans[N];
int tot,head[N],ver[M],ne[M];
int pre[N];
priority_queue<PII>Q;
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void Dijkstra()
{
    ver[++tot]=1;
    Q.push({1,tot});
    while(!Q.empty())
    {
        int x=Q.top().second,y=ver[x];
        Q.pop();
        if(pre[y])continue;
        pre[y]=x;
        for(int i=head[y];i;i=ne[i])Q.push({a[i],i});
    }
}
int main()
{
    read(n,m,q);
    for(int i=1;i<=m;i++)read(u[i],v[i]),add(u[i],v[i]),a[i]=q+1;
    for(int i=1,x;i<=q;i++)
    {
        read(x);
        if(a[x]>i)ans[a[x]=i]=1;
        else ans[i]=0;
    }
    Dijkstra();
    for(int i=n;i!=1;i=u[pre[i]])ans[a[pre[i]]]=0;
    for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
    return 0;
}