2023-01-08

题目算法

解题思路

首先就想到暴力 dp，用三个循环枚举：\(1.\) 时间，\(2.\) 目前在的城市，\(3.\) 明天去的城市。时间复杂度为 \(O(n^2k)\)，由于 \(1 \le n,m,k \le 5000\)，所以会超时。
后来想到边表可以优化边，于是就用边表记录不能走的，\(f_{i,j}\) 就是加上之前所有的方案数 \(f_{i-1,j}\) 再减去不能走的（包括自己）。虽然看上去没什么区别，但是因为只有 \(M\) 条边，所以只用算 \(2M\) 次（因为是双向的）。最终的时间复杂度为 \(O(nm+nk)\)。

完成状态

已完成

Code

#include<bits/stdc++.h>
#define int long long
#define Mod 998244353
#define N_5 100005
#define For(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
int n,m,k;
int u[N_5],v[N_5];
int f[5005][5005];
vector<int>a[N_5];
signed main(){
	cin>>n>>m>>k;
	For(i,1,m){
		cin>>u[i]>>v[i];
		a[u[i]].push_back(v[i]);
		a[v[i]].push_back(u[i]);
	}f[0][1]=1;
	For(i,1,k){
		int sum=0;
		For(j,1,n)sum+=f[i-1][j]; 
		For(j,1,n)f[i][j]+=sum-f[i-1][j];
		For(j,1,n){
			int len=a[j].size()-1;
			For(k,0,len)
				f[i][j]-=f[i-1][a[j][k]];
			f[i][j]=(f[i][j]+Mod)%Mod;
		}
	}
	cout<<f[k][1]%Mod;
	return 0;
}