[NOIP2017]逛公园

发布于 2017-12-03  87 次阅读



题目(洛谷)
NOIP每年至少一道dp题,然后就考在这道题目上了.
......从这道题开始我就zz了.
看k的数据范围,50以内,嗯,可以做dp.
dp[i][k]表示当前在第i个点,超过i到n的最短距离dis[i]的长度k时的路线条数。
于是方程就很好写了,dp[u][k]+=dp[v][dis[u]+k-dis[v]-w]
初值:dp[1][0]=1。
整个记忆化搜索就行。
然后这个题是个有向图,而且还有环存在,所以我们考虑倒着推过去。
从n开始向1推着走,记录当前状态是否被更新,如果当前状态已访问过再去更新,则说明有0的环存在,输出-1;
注意最后还要来一次dfs(n,k+1),用以判断0环。
答案就是∑dfs(n,i),0<=i<=k。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#define readf(f) scanf(
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
template <class _E> inline void read(_E &e)
{
    e=0;bool ck=0;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
    if(ck)e=-e;
}
int n,m,k;
ll mod;
struct edge{
    int vk;
    int wk;
    int nxt;
}e[200005],f[200005];
int t=0,t2=0,head[100005],hd2[100005];
inline void ad(int u,int v,int w)
{
    e[++t].vk=v;
    e[t].wk=w;
    e[t].nxt=head[u];
    head[u]=t;
    f[++t2].vk=u;
    f[t2].wk=w;
    f[t2].nxt=hd2[v];
    hd2[v]=t2;
}
int dis[100005];
bool vis[100005],ac[100005][55];
ll dp[100005][55],ans;
bool no;
inline void data_clear();
inline void sp()
{
    queue <int> q;
    q.push(1);
    dis[1]=0,vis[1]=1;
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for (int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].vk;
            int w=e[i].wk;
            if (dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if (!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
ll dfs(int u,int kk)
{
    if (no) return 0;
    if (~dp[u][kk]) return dp[u][kk];
    ac[u][kk]=1;
    dp[u][kk]=0;
    for (int i=hd2[u];i;i=f[i].nxt)
    {
        int v=f[i].vk;
        int w=f[i].wk;
        int nxk=dis[u]+kk-dis[v]-w;
        if (nxk<0) continue;
        if (ac[v][nxk])
        {
            no=true;
            return 0;
        }
        dp[u][kk]+=dfs(v,nxk),dp[u][kk
    }
    ac[u][kk]=0;
    return dp[u][kk];
}
int main()
{
    int T;
    read(T);
    while (T--)
    {
        data_clear();
        read(n),read(m),read(k),read(mod);
        for (int i=1;i<=m;++i)
        {
            int x,y,z;
            read(x),read(y),read(z);
            ad(x,y,z);
        }
        sp();
        dp[1][0]=1;
        for (int p=0;p<=k;++p)
        {
            ans+=dfs(n,p),an
            if (no) break;
        }
        if (no)
        {
            puts("-1");
            continue;
        }
        dfs(n,k+1);
        if (no)
        {
            puts("-1");
            continue;
        }
        cout<<ans<<endl;
    }
    return 0;
}
inline void data_clear()
{
    ans=t=t2=0,no=false;
    memset(dp,-1,sizeof dp);
    memset(vis,0,sizeof vis);
    memset(hd2,0,sizeof hd2);
    memset(dis,inf,sizeof dis);
    memset(ac,0,sizeof ac);
    memset(head,0,sizeof head);
}

来说说我是怎么zz的吧。
dp[i][k]我表示的是当前在第i点,超过dis[n]的长度为k的方案数。
GG.