专栏文章

题解：P3953 [NOIP2017 提高组] 逛公园

CCJZJC
P3953题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miqg0mqy
此快照首次捕获于
2025/12/04 04:11
3 个月前
此快照最后确认于
2025/12/04 04:11
3 个月前
查看原文

前言

可能是实现方法最详细的一片题解。我是黑暗贝利亚奥特曼，能踩的坑我都帮你们踩了。
题目传送门

题解

sub 1,2,7

当 K=0K=0，且没有 00 边时，此题就退化成了最短路计数。可以看看这道题：P1144。

sub 1,2,3,4,5,7,8

考虑边权不为 00 的情况，可以发现这是很好想的一个 DP。
具体来说，我们令 disidis_i 为 11 到 ii 最短路径的长度。fi,jf_{i,j} 表示当前节点为 ii，路径长度为 disi+jdis_i+j，这时图变成了一个 DAG，则我们可以写出转移式：
fi,j=∑v∣(u,v)∈E′fk,disi+j−w−diskf_{i,j} = \sum_{v|(u,v)\in E'} f_{k,dis_i+j-w-dis_k}
初始时 f1,0=1f_{1,0}=1，答案即为 ∑i=1kfn,i\sum_{i=1}^k f_{n,i}。
该 DP 可以用记忆化搜索或拓扑排序实现。
显然，在边权不为 00 时，该 DP 不会有后效性。

正解

考虑在何种情况下答案会有无穷种。由刚才的 DP 可以发现，如果在 DP 时出现了一个由 00 构成的环时，会有无穷种答案。
考虑如何判断。
方案一：我们可以把所有边权为 00 的边建一张图，在上面跑 tarjan 缩点，这样就形成了一张 DAG。再在 DAG 上跑一遍拓扑，看 11 到 nn 的路径上是否有大小超过 11 的强连通分量，如果有显然会有无穷种答案。
方案二：我们在跑记忆化搜索时，如果从一个点出发还能搜到这一个点，就会有无穷种答案。于是可以在搜索时用一个数组记录一个状态是否在搜索中，如果它已经被搜过就返回 −1-1，这样就完成了判断。

几个坑点

由于本人太菜，在做题时错了很多次，在摸索的过程中才把正解探究出来。
  1. 在求 ff 数组前要跑一遍 dij，且 ff 数组不能直接在 dij 中求出来。
  2. 在记忆化搜索时，要判断 fi,jf_{i,j} 中的 jj 是否满足 0≤j≤K0\leq j \leq K，尤其是要判断 j≥0j\geq 0（感谢 @LLCCFF 的指出），这一种情况很容易漏掉。
  3. 如果你是记忆化搜索，在把 f1,0f_{1,0} 设为 11 前，先要搜索一下 f1,0f_{1,0} 是否有无穷种答案（其实样例就可以测出来）。
  4. 最根本的问题。检查你的 dij 是否出错（比如使用了大根堆、没有 visvis 数组）！
  5. 记得取模 PP。
  6. 多测清空（用样例应该也能测出来）。

代码

缩点 + 拓扑排序的做法是口胡的，就不放代码了。
这份代码使用了上文中的记忆化搜索，记忆化搜索时的传参与 ff 的状态设计稍有不同。
CPP
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int T,n,m,k,p,dis[N],f[N][51];
bool ins[N][51],fl,vis[N];
vector<pair<int,int>>to[N],to2[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q; //注意是小根堆
int calc(int x,int ds){ //记忆化搜索
	if(fl){ //如果有无穷种答案，直接返回
		return 0;
	}
	if(ds<dis[x]){ //一定要注意！
		return 0;
	}
	if(ds>dis[x]+k){
		return 0;
	}
	if(ins[x][ds-dis[x]]){ //判断是否访问到自己
		fl=1;
		return 0;
	}
	if(f[x][ds-dis[x]]!=-1){ //记忆化，注意没有访问到的状态应设为 -1
		return f[x][ds-dis[x]];
	}
	ins[x][ds-dis[x]]=1;
	f[x][ds-dis[x]]=0;
	for(auto [y,w]:to2[x]){
		f[x][ds-dis[x]]=(f[x][ds-dis[x]]+calc(y,ds-w))%p; //记得取模
	}
	ins[x][ds-dis[x]]=0;
	return f[x][ds-dis[x]];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--){
		fl=0;
		cin>>n>>m>>k>>p;
		for(int i=1;i<=n;i++){ //多测要清空
			to[i].clear();
			to2[i].clear();
			vis[i]=0;
		}
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			to[u].push_back(make_pair(v,w));
			to2[v].push_back(make_pair(u,w)); //记忆化搜索是在反图上进行
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<=k;j++){
				f[i][j]=-1;
			}
			dis[i]=1e10;
		}
		dis[1]=0;
		q.push(make_pair(0,1));
		while(!q.empty()){ //先求出最短路
			int x=q.top().second;
			q.pop();
			if(vis[x]){
				continue;
			}
			vis[x]=1;
			for(auto [y,w]:to[x]){
				if(dis[x]+w<dis[y]){
					dis[y]=dis[x]+w;
					q.push(make_pair(dis[y],y));
				}
			}
		}
		calc(1,0);
		f[1][0]=1;
		int ans=0;
		for(int i=0;i<=k;i++){
			ans=(ans+calc(n,dis[n]+i))%p; //统计答案
		}
		if(fl){
			cout<<-1<<'\n'; //判断答案是否有无穷种
			continue;
		}
		cout<<ans<<'\n';
	}
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...