题解 P3953 【逛公园】

xzyxzy

2018-06-07 21:39:56

Solution

~~Noip炸~,于是我到现在才开始更正题目。。~~ # 记忆化搜索做法 这种题目一点也不套路,很不好做,甚至我看了一个小时题解才弄懂 那么首先看K很小,所以可以把K纳入状态中 令dp[i][j]表示到i号节点,还有j的值可以去绕弯路的方案数(不一定j要绕完,可以绕0~j之间的弯路) 那么答案就是dp[N][K] ### 全程序分为三个部分 #### 一、读入 略 #### 二、预处理每个点到1的最短路 略 #### 三、反向建图后记搜答案 假设在原图中有一条x->y,w的边 那么从x走到y就是dis[x]+w 实际上最短路是dis[y] 那么绕弯路的长度是 (dis[x]+w)-dis[y] 所以DFS(x,res)表示到达x点还剩res步可以绕的方案数 $$ dp[x][res]=\sum_{y,y->x}dp[y][res-(dis[x]+w-dis[y])] $$ 边界条件是到达1返回1 判断环的情况在代码中有提到 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> using namespace std; int read() { char ch=getchar();int h=0,t=1; while((ch>'9'||ch<'0')&&ch!='-') ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar(); return h*t; } const int MAXN=210000; int T,N,M,K,mod,cnt,head[MAXN]; int fr[MAXN],to[MAXN],w[MAXN]; int dis[MAXN],vis[MAXN],dp[MAXN][51]; int in[MAXN],re[MAXN],flag; queue<int> Q; struct edge{int next,to,w;}a[MAXN<<1]; void link(int x,int y,int w) { a[++cnt]=(edge){head[x],y,w}; head[x]=cnt; } int DFS(int x,int res)//返回到达x点还剩res步可以绕的方案数 { if(~dp[x][res]) return dp[x][res]; dp[x][res]=(x==1); for(int i=head[x];i;i=a[i].next) { int R=a[i].to; int tt=res-((dis[R]+a[i].w)-dis[x]);//通过这条边多绕了一会 if(tt<0) continue; if(in[R]&&re[R]==tt) flag=1;//如果说res一直没有减少的情况下搜出来一个圈,说明有0环 else in[R]=1,re[R]=tt; (dp[x][res]+=DFS(R,tt))%=mod; in[R]=0;re[R]=0; } return dp[x][res]; } void Work() { //Part 1 初始化/读入 memset(head,0,sizeof(head));cnt=0; N=read();M=read();K=read();mod=read(); for(int i=1;i<=M;i++) { fr[i]=read();to[i]=read();w[i]=read(); link(fr[i],to[i],w[i]); } //Part 2 SPFA预处理距离 memset(dis,63,sizeof(dis)); Q.push(1);dis[1]=0;vis[1]=1; while(!Q.empty()) { int x=Q.front(); for(int i=head[x];i;i=a[i].next) { int R=a[i].to; if(dis[R]<=dis[x]+a[i].w) continue; dis[R]=dis[x]+a[i].w; if(!vis[R]) vis[R]=1,Q.push(R); } Q.pop();vis[x]=0; } //Part 3 建反图DFS记搜 memset(head,0,sizeof(head));cnt=0; memset(dp,-1,sizeof(dp));flag=0; for(int i=1;i<=M;i++) link(to[i],fr[i],w[i]); DFS(N,K); printf("%d\n",flag?-1:DFS(N,K)); } int main() { T=read();while(T--)Work(); } ``` ~~安利一波[博客](https://www.cnblogs.com/xzyxzy/)吧。。(逃~~