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

· · 题解

前言

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

题目传送门

题解

sub 1,2,7

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

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

考虑边权不为 0 的情况，可以发现这是很好想的一个 DP。

具体来说，我们令 dis_i 为 1 到 i 最短路径的长度。f_{i,j} 表示当前节点为 i，路径长度为 dis_i+j，这时图变成了一个 DAG，则我们可以写出转移式：

f_{i,j} = \sum_{v|(u,v)\in E'} f_{k,dis_i+j-w-dis_k}

初始时 f_{1,0}=1，答案即为 \sum_{i=1}^k f_{n,i}。

该 DP 可以用记忆化搜索或拓扑排序实现。

显然，在边权不为 0 时，该 DP 不会有后效性。

正解

考虑在何种情况下答案会有无穷种。由刚才的 DP 可以发现，如果在 DP 时出现了一个由 0 构成的环时，会有无穷种答案。

考虑如何判断。

方案一：我们可以把所有边权为 0 的边建一张图，在上面跑 tarjan 缩点，这样就形成了一张 DAG。再在 DAG 上跑一遍拓扑，看 1 到 n 的路径上是否有大小超过 1 的强连通分量，如果有显然会有无穷种答案。

方案二：我们在跑记忆化搜索时，如果从一个点出发还能搜到这一个点，就会有无穷种答案。于是可以在搜索时用一个数组记录一个状态是否在搜索中，如果它已经被搜过就返回 -1，这样就完成了判断。

几个坑点

由于本人太菜，在做题时错了很多次，在摸索的过程中才把正解探究出来。

  1. 在求 f 数组前要跑一遍 dij，且 f 数组不能直接在 dij 中求出来。

  2. 在记忆化搜索时，要判断 f_{i,j} 中的 j 是否满足 0\leq j \leq K，尤其是要判断 j\geq 0（感谢 @LLCCFF 的指出），这一种情况很容易漏掉。

  3. 如果你是记忆化搜索，在把 f_{1,0} 设为 1 前，先要搜索一下 f_{1,0} 是否有无穷种答案（其实样例就可以测出来）。

  4. 最根本的问题。检查你的 dij 是否出错（比如使用了大根堆、没有 vis 数组）！

  5. 记得取模 P。

  6. 多测清空（用样例应该也能测出来）。

代码

缩点 + 拓扑排序的做法是口胡的，就不放代码了。

这份代码使用了上文中的记忆化搜索，记忆化搜索时的传参与 f 的状态设计稍有不同。

#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';
    }
}