$[NOIp2017]$ 逛公园 $dp$/记搜

$Des$

给定一个有向图,起点为$1$,终点为$n$,求和最短路相差不超过$k$的路径数量.有$0$边.如果有无数条,则输出$-1$.

$n\leq 10^5,k\leq 50$

$Sol$

首先,有无数条边的情况一定是在与最短路相差不超过$k$的一条路上有$0$环.

先不考虑$0$边和$0$环,$get\ 70pts$做法:先跑一个最短路,$dis[i]$表示从$1$到$i$的最短路径.记$f[u][k]$表示从$1$到$u$路径长度不超过$dis[u]+k$的路径条数,$f[u][k]$显然是转移到$f[v][dis[u]+k+w(u,v)-dis[v]]$.转移顺序显然是从$dis$小的转移到$dis$大的,直接按$dis$从小到大的顺序.于是一个$O(NK)$的$dp$就出炉了.

考虑正解.

首先看怎么判断无穷解.记$f_i$为$1$到$i$的最短路,$g_i$为$i$到$n$的最短路.判断无穷解:先把所有可行的$0$边拎出来,再看它们是不是组成了环.一条边$(i,j)$可行当且仅当$f_i+g_j+w\leq f_n+k$.于是这里就可以简单判断了.

接下来仍然是$dp$,但是因为$0$边的存在所以并不能直接按$dis$从小到大的顺序转移,我们需要另外一种方法来确定$0$边两个端点的转移顺序.考虑把所有可行的$0$边的两个端点拎出来,然后拓扑排序.最后对于所有的点,只需要按照$f$为第一关键字,拓扑排序排出来的顺序为第二关键字排序,按照这个顺序更新即可.

其实还有更加简单的记忆化搜索的写法:

$dfs(u,res)$表示已经从$1$号结点跑到$u$结点,还有可以比最短路多走$res$的长度,走到$n$结点的方案数.显然这里需要跑一个反向最短路$dis$.答案是$\sum dfs(v,res-(dis_v+w-dis_u))$.记忆化一下即可.

怎么判断$0$环呢?只需要记一个$stk_{u,res}$表示在搜索树中当前结点的祖先结点们有没有出现过这个状态,如果有,那么就一定有$0$环.

我永远喜欢记搜!

对了,还看到一个非常神仙的分层图求法.在这里.

$Code$

#include<bits/stdc++.h>

#define il inline

#define Ri register int

#define go(i,a,b) for(Ri i=a;i<=b;++i)

#define yes(i,a,b) for(Ri i=a;i>=b;--i)

#define e(i,u) for(Ri i=b[u];i;i=a[i].nt)

#define mem(a,b) memset(a,b,sizeof(a))

#define ll long long

#define db double

#define inf 2147480000

#define pr pair<int,int>

#define mp make_pair

#define fi first

#define sc second

using namespace std;

il int read()

{

    Ri x=0,y=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}

    return x*y;

}

const int N=1e5+5;

int n,m,k,p,b[N],ct,dis[N],as,rem[N][55];

bool fl,stk[N][55];

priority_queue<pr>q;

struct nd{int v,w,nt;}a[N*2];

struct ed{int u,v,w;}e[N*2];

il void add(Ri u,Ri v,Ri w){a[++ct]=(nd){v,w,b[u]};b[u]=ct;}

il void inc(Ri &x,Ri y){x+=y;if(x>=p)x-=p;}

il void dijkstra()

{

    go(i,1,n-1)dis[i]=inf;

    dis[n]=0;q.push(mp(0,n));

    while(q.size())

    {

	    Ri u=q.top().sc,d=-q.top().fi;q.pop();

	    if(d>dis[u])continue;

	    e(i,u)

	    {

	        Ri v=a[i].v,w=a[i].w;

	        if(d+w<dis[v]){dis[v]=d+w;q.push(mp(-dis[v],v));}

	    }

    }

}

il int dfs(Ri u,Ri res)

{

    if(stk[u][res]){fl=1;return 0;}

    if(rem[u][res])return rem[u][res];

    stk[u][res]=1;Ri ret=0;

    e(i,u)

    {

	    Ri v=a[i].v,w=a[i].w,tmp=res-(dis[v]+w-dis[u]);

	    if(tmp>=0)inc(ret,dfs(v,tmp));

	    if(fl)return 0;

    }

    stk[u][res]=0;return rem[u][res]=ret;

}

int main()

{

    Ri T=read();

    while(T--)

    {

	    n=read(),m=read(),k=read(),p=read(),as=0,fl=0;

	    go(i,1,m)e[i]=(ed){read(),read(),read()};

	    mem(b,0);ct=0;

	    go(i,1,m)add(e[i].v,e[i].u,e[i].w);

	    dijkstra();

	    mem(b,0);ct=0;

	    go(i,1,m)add(e[i].u,e[i].v,e[i].w);

	    mem(stk,0);mem(rem,0);rem[n][0]=1;

	    go(i,0,k){inc(as,dfs(1,i));if(fl)break;}

	    if(fl)printf("-1\n");

	    else printf("%d\n",as);

    }

    return 0;

}

巴特西

$[NOIp2017]$ 逛公园 $dp$/记搜

\(Des\)

\(Sol\)

\(Code\)

最新文章

热门文章