题解：P8860 动态图连通性

· · 题解

题目

更好的阅读体验

题意

每次询问一条边 x，然后假设把这条边删掉，看看还能不能从 1 走到 n，能走到，就真删掉，输出 1；不能走到，就保留这条边，输出 0。注意，成功删掉的边，以后就一直不存在了。

思路

根据题意，我们思考，假如我们能提前确定一条从 1 到 n 的路径，并保证这条路径上的边始终保留，那么：

于是，问题就转化成了：如何提前确定一条能够在整个过程中保留下来的 1\to n 路径？

所以我们可以先将每条边的第一次被询问时间离线下来。

设 d_{i} 表示原图第 i 条边第一次被询问的时刻。如果它从未被询问，则令 d_{i}=q+1。

嘶，这是我们可以发现一个显然的性质：一条边第一次被询问时，如果它不能被删除，那么它以后也不可能被删除。因为图中只会不断删除边，并不会增加边，既然现在删掉它会导致 1 无法到达 n，之后删掉更多边只会让情况更差。

因此，每条边只需考虑它第一次被询问的时刻。

我们把 d_i 当作这条边的优先级：

于是，我们肯定希望找到一条优先级尽可能高的 1\to n 路径。

那么如何找呢？

我们可以把每条边的首次询问时间 d_{i} 当作边权，然后用大根堆优先扩展搜索。也就是优先考虑由较晚才会被询问的边到达的点。

同时在搜索时，我们维护 vis_{u}（表示点 u 是否已经处理）、pre_{v}（到达点 v 的前一个点）、p_{v}（到达点 v 使用的原图边编号）。

当发现一条更晚才会被询问的边可以进入点 v 时，就更新 pre_{v}、p_{v}，并把 v 放进堆里。搜索到终点 n 后，就可以沿着 pre 从 n 倒着走回 1，还原出需要保留的路径。

然后我们解释一下为什么这样找是可以的：

首先我们把搜索得到的路径记为 P。

因为搜索的过程优先扩展首次询问时间较大的边，所以构造出的路径具有这样的性质：

OK，那么现在考虑询问时刻 t，尝试删除路径上的边 e：

所以，删除 e 会破坏从 1 到 n 的连通路径，应该保留。

反过来，对于不在 P 上的边，即使删除它，路径 P 仍然完整存在，所以它可以删除。

这样就说明了为什么我们可以这么找。

以上就是我的全部思路，其他的详见代码吧。

代码如下

/*@author:decentz*/
#include<bits/stdc++.h>
#define FRE(x,y) freopen(#x".in","r",stdin);freopen(#y".out","w",stdout);
#define LK_TIME cerr<<(1.0*clock()/CLOCKS_PER_SEC)<<'\n';
#define REP(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define PRE(i,a,b) for(int i=(a),i##end=(b);i>=i##end;i--)
#define MMS(arr,n) memset(arr,n,sizeof(arr));
#define DEBUG(x) cerr<<#x<<": "<<x<<'\n';
using namespace std;
using LL=long long;
const LL INF=LLONG_MAX,_INF=LLONG_MIN;
bool STWZZ;
const int N=2e5+5;
int n,m,q,hd[N],nxt[N],ver[N],t[N],tot,d[N],ask[N],pre[N],p[N];
priority_queue<pair<int,int>> pq;//存边的优先级,点的编号
bool vis[N],kp[N];//kp表示原图第i条边是否在选出的保留路径上
void add(int u,int v,int i){
    ver[++tot]=v;nxt[tot]=hd[u];t[tot]=i;hd[u]=tot;
}
void sou(){
    pq.push({0,1});
    while(pq.size()){
        int u=pq.top().second;pq.pop();
        if(vis[u]) continue;
        if(u==n) break;//如果已经取出终点n，就停止搜索，因为已经找到一条从1到n的路径。
        vis[u]=true;
        for(int i=hd[u];i;i=nxt[i]){
            int v=ver[i];
            if(!vis[v]&&d[t[i]]>d[p[v]]){//点v还没有被确定处理，并且当前这条边的删除时间更晚，也就是优先级更高。
                p[v]=t[i];//记录进入v的新边
                pre[v]=u;
                pq.push({d[t[i]],v});
            }
        }
    }
}
bool EDWZZ;
int main(){
    //FRE(,);
    //cerr<<(&EDWZZ-&STWZZ)/1024.0/1024.0<<'\n';
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    REP(i,1,m){
        int u,v;cin>>u>>v;
        add(u,v,i);
        d[i]=q+1;
    }
    REP(i,1,q){
        cin>>ask[i];
        d[ask[i]]=min(d[ask[i]],i);
    }
    sou();
    for(int u=n;u!=1;u=pre[u]) kp[p[u]]=true;//把保留路径上的边标记出来
    REP(i,1,q){
        if(d[ask[i]]==i&&!kp[ask[i]]) cout<<1<<'\n';//它能够被删除，当且仅当：这是它第一次被询问，并且它不在保留路径上。
        else cout<<0<<'\n';
    }
    return 0;
}
//时间复杂度分析：每条边只在建图时加入一次，每次询问只处理常数次；搜索过程中，边可能让端点进入优先队列，优先队列操作需要O(log n)。
//因此时间复杂度为O((n+m+q)log n)。