AtCoder Beginner Contest 212 E(DP)

AtCoder Beginner Contest 212

ABC 212

E - Safety Journey

题意

一个完全图（即任意两点之间都有一条双向道路），给定$m$条废弃的道路，问从$1$号城市出发走$k$步走回$1$号的方案有多少种。

思路

观察数据范围$n<=5000$ $m<=5000$ $k<=5000$可以考虑二维暴力DP 。
定义DP数组 $f[i][j]$ : 第$i$步走到城市$j$的方案数
对于每一步枚举从城市$k$出发,可以得到dp方程 $f[i][j]={\sum }_{k=1}^{n}f[i-1][k]$(城市$k$到城市$j$的道路存在且还没有废弃)
估计时间复杂度 因为枚举步数,出发城市,存在的道路都是O(n)的 循环嵌套时间复杂度为$O(n^3)$ 显然不足以通过此题。

考虑如何优化，因为dp方程的定义已经确定，所以只能从枚举每个城市连接的道路着手。
时间复杂度在于，因为是完全图删去的道路最多为$5000$条,所以对于每个城市直接连接的城市仍然有很多。
正难则反，因为删去的道路很少，我们可以枚举出发城市$k$所不能到达的城市，而不是能到达的城市。

在前一次dp求解中记录下 $sum={\sum }_{j=1}^{n}f[i-1][j]$ 在枚举城市$k$时 $sub={\sum }_{k=1}^{n}f[i-1][j]$($k$不能到达$j$)
那么答案就是$f[i][j]={\sum }_{k=1}^{n}f[i-1][k]$(城市$k$到城市$j$的道路存在且还没有废弃) $=sum-sub$
因为删除的道路很少，在每次循环中遍历的次数之和恰好为$m\ast 2$
时间复杂度优化到$O(n\ast m)$

代码

#include 
#include 
#include 
using namespace std;
#define ll long long
const int N = 5010, mod = 998244353;
int n,m,k;
int f[N][N];//第i步走到j地的方案
vector<int>g[N];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= m; i ++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    f[0][1] = 1;
    ll sum = 1;//f[i - 1]的道路方案数总和
    for(int i = 1; i <= k; i ++)
    {
        ll tmp = 0;
        for(int j = 1; j <= n; j ++)
        {
            ll sub = f[i - 1][j];//道路废弃的城市方案数减去,初始化为f[i-1][j]因为自己不能到自己
            for(int v : g[j]){
                sub = (sub + f[i - 1][v]) % mod;
            }
            f[i][j] = (sum + mod - sub) % mod;
            tmp = (tmp + f[i][j]) % mod;//记录sum
        }
        sum = tmp;
    }
    printf("%d\n",f[k][1]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

更新：
E:2022.11.4
F待补