AT_abc319_g [ABC319G] Counting Shortest Paths

· · 题解

最短路、动态规划

好题，场上写的做法 TLE 了五个点，所以写一篇题解。

我是不是已经退役一个月了。

2023/9/11：更正了由 AcO2d 指出的语义混淆。

题意

在有 n 个节点的无向完全图上删除 m 条边，判断节点 1 和节点 n 是否连通。

若节点 1 和节点 n 不连通，输出 -1。

否则输出节点 1 到节点 n 的最短路数量对 998244353 取模的值。

分析

以下所有讨论的对象均为原图。

建出原图的时间复杂度为 O(n^2)，不可接受。考虑一个稠密图遍历方法：对于点 i，记录所有与其未连边的点。记录所有未被遍历的点，形成一个集合。

初始时将起点入队，在未被遍历的点的集合中删除起点。

遍历未被遍历的点的集合并查询点 i 与队首之间是否未连边，如果连边，那么在未被遍历的点的集合中删除点 i，更新 i 到起点的距离并将 i 入队。

由于指定删除的边数量至多 2 \times 10^5 条，至多 2 \times 10^5 次查询结果为未连边，否则点 i 将会入队。也就是说，起点可达的所有点全部入队之前至多进行 4 \times 10^5 次查询。

由于 n、m 同阶，在使用 unordered_set 的情况下，这一部分的时间复杂度为 O(n)。

既然最短路长度已经求得，是不是可以连边后拓扑排序计算其数量了？否。即使边数有所减少，连边的代价仍然是不可接受的。

令 dis_i 为节点 i 到节点 1 的最短距离。对于点对 u,v，只有在 dis_u=dis_v+1 或 dis_v=dis_u+1 时相互之间产生贡献。

原图中几乎所有符合以上条件的点对之间存在贡献。

对于 dis=i+1 的点 u，将其答案初始化为所有 dis=i 的点的答案之和，因为几乎所有 dis=i 的点都可以到达点 u。然后枚举所有与 u 未连边的点 v，如果符合 dis_u=dis_v+1 就将 v 的答案从 u 的答案中扣除。

总体时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998244353;
vector<int> e[200005],v[200005];
int n,m,dp[200005],dis[200005];
unordered_set<int> s,w[200005];
queue<int> q;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) s.emplace(i);
    for(int i=1;i<=m;i++){
        static int x,y;
        scanf("%d%d",&x,&y);
        w[x].emplace(y);//bfs时查询连边用 
        w[y].emplace(x);
        v[x].push_back(y);//计算最短路数量用 
        v[y].push_back(x);
    }
    dp[1]=1,dis[1]=1,s.erase(1);
    for(q.push(1);!q.empty();q.pop()){
        vector<int> trash;
        int now=q.front();
        for(int i:s) if(!w[now].count(i)){
            dis[i]=dis[now]+1;
            q.push(i);
            trash.push_back(i);
        }
        for(int i:trash) s.erase(i);
    }
    if(dis[n]==0) return puts("-1"),0;
    for(int i=1;i<=n;i++) e[dis[i]].push_back(i);
    for(int i=2;i<=dis[n];i++){
        long long sum=0ll;
        for(int j:e[i-1]) sum+=dp[j];//完全图在任意点之间都有连边 
        for(int j:e[i]){//枚举dis[j]=i的点 
            long long ans=sum;
            for(int k:v[j]) if(dis[k]==dis[j]-1) ans-=dp[k];//减去没有连边的点的贡献 
            dp[j]=(ans%mod+mod)%mod;
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}