@ysner 2018-11-02T23:52:19.000000Z 字数 6522 阅读 1676

noip2017逛公园

图论 拓扑排序 DP 最短路

题面

无人不知，无人不晓。

解析

这绝对是 $noip2017$ 得分最难的题目。

$30pts$ 算法

最短路计数？跑 $Dijstra$ 的同时，顺便 $DP$ 算下方案数就好。
于是设 $f[i]$ 表示由 $1$ 到 $i$ 点的方案数。

#define pi pair<int,int>
#define mk make_pair
#define fi first
#define se second
priority_queue<pi,vector<pi>,greater<pi> >Q;
il void Dijstra()
{
  fp(i,1,n) dis[i]=1e9,vis[i]=0;
  dis[1]=0;Q.push(mk(0,1));
  while(!Q.empty())
    {
      re int u=Q.top().se;Q.pop();
      vis[u]=1;
      for(re int i=h[u];i+1;i=e[i].nxt)
      {
        re int v=e[i].to;
        if(dis[v]>dis[u]+e[i].w)
    {
      dis[v]=dis[u]+e[i].w;f[v]=f[u];
      Q.push(mk(dis[v],v));
    }
    else if(dis[v]==dis[u]+e[i].w) (f[v]+=f[u])%=mod;
      }
      while(!Q.empty()&&vis[Q.top().se]) Q.pop();
    }
}

$70pts$ 算法

考虑到 $k$ 很小，可以把 $k$ 加入状态。
于是设 $dp[j][i]$ 表示到达 $i$ 点，路径长度比最短路长 $j$ 的方案数。
看这个状态就知道我们要预处理最短路。
~~状态都会设，正确转移估计没多少人会了~~

显然转移式为

$dp[j][u]=\sum dp[dis_u+j-e[i].w-dis_v][v]$

但是题目背景是张图， $DP$ 时是要考虑转移顺序的。

由于在转移过程中， $j$ 这一维一定是单调不降的，那么肯定是由 $j$ 小的状态往 $j$ 大的状态转移。
但是这样还不止，你会发现只这么写会过不了某个样例。。。而且这个样例的 $k=0$ 。。。

注意到 $j$ 相等的转移（在最短路上的转移）是有锅的。
其实这一类型的转移，我们都是由 $dis$ 值小的转移到 $dis$ 值大的，这一点看看 $30pts$ 最短路计数的转移就应该明白。
那么这里也一样，给所有点依 $dis$ 排个序，~~这就是转移的拓扑序~~。
然后像拓扑排序那样转移就行，由一个节点向与其相连的多个结点转移。

于是就有 $70pts$ 了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define pi pair<int,int>
#define mk make_pair
#define fi first
#define se second
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=1e5+100;
int f[55][N],n,m,k,mod,h[N],cnt,dis[N],ans,sta[N];
bool vis[N];
struct Edge{int to,nxt,w;}e[N<<1];
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Dijstra()
{
  priority_queue<pi,vector<pi>,greater<pi> >Q;
  fp(i,1,n) dis[i]=1e9,vis[i]=0;
  dis[1]=0;Q.push(mk(0,1));
  while(!Q.empty())
    {
      re int u=Q.top().se;Q.pop();
      vis[u]=1;
      for(re int i=h[u];i+1;i=e[i].nxt)
      {
        re int v=e[i].to;
        if(dis[v]>dis[u]+e[i].w)
    {
      dis[v]=dis[u]+e[i].w;
      Q.push(mk(dis[v],v));
    }
      }
      while(!Q.empty()&&vis[Q.top().se]) Q.pop();
    }
}
il void Dp()
{
  fp(j,0,k)
  fp(o,1,n)
    {
      re int u=sta[o];
    for(re int i=h[u];i+1;i=e[i].nxt)
      {
    re int v=e[i].to;
        if(dis[u]+j-dis[v]+e[i].w>=0&&dis[u]+j-dis[v]+e[i].w<=k)
    (f[dis[u]+j-dis[v]+e[i].w][v]+=f[j][u])%=mod;
      }
    }
}
il bool cmp(re int x,re int y){return dis[x]<dis[y];}
int main()
{
  re int T=gi();
  while(T--)
  {
    memset(h,-1,sizeof(h));memset(f,0,sizeof(f));cnt=0;ans=0;
    n=gi();m=gi();k=gi();mod=gi();
    fp(i,1,m)
      {
    re int u=gi(),v=gi(),w=gi();
    add(u,v,w);
      }
    Dijstra();
    fp(i,1,n) sta[i]=i;sort(sta+1,sta+1+n,cmp);
    f[0][1]=1;
    Dp();
    fp(i,0,k) (ans+=f[i][n])%=mod;
    printf("%d\n",ans);
  }
  return 0;
}

$100pts$ 算法

有 $0$ 边时转移又锅了。
因为会有 $dis$ 和 $j$ 同时相等的点，它们谁先转移，谁后转移需要进一步确定。
仔细想想，发现按拓扑序转移就行了，毕竟只有这样才满足无后效性。

那就进行一遍拓扑排序（只有 $0$ 边提供入度，因为针对 $dis$ 和 $j$ 同时相等的点）。
如果跑完后还有点没进拓扑序，说明有 $0$ 环。
如果有合法路线经过 $0$ 环，就可以 $puts("-1")$ 了（~~但实际上GGF的数据中，只要有零环就可以puts~~）。
然后再两重标准给点排序，再照搬 $70pts$ 转移即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define pi pair<int,int>
#define mk make_pair
#define fi first
#define se second
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=1e5+100;
int f[55][N],n,m,k,mod,h[N],cnt,dis[N],ans,sta[N],d[N],seq[N],top;
bool vis[N],lab[N];
struct Edge{int to,nxt,w;}e[N<<1];
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Dijstra()
{
  priority_queue<pi,vector<pi>,greater<pi> >Q;
  fp(i,1,n) dis[i]=1e9,vis[i]=0;
  dis[1]=0;Q.push(mk(0,1));
  while(!Q.empty())
    {
      re int u=Q.top().se;Q.pop();
      vis[u]=1;
      for(re int i=h[u];i+1;i=e[i].nxt)
      {
        re int v=e[i].to;
        if(dis[v]>dis[u]+e[i].w)
    {
      dis[v]=dis[u]+e[i].w;
      Q.push(mk(dis[v],v));
    }
      }
      while(!Q.empty()&&vis[Q.top().se]) Q.pop();
    }
}
il void Dp()
{
  fp(j,0,k)
  fp(o,1,n)
    {
      re int u=sta[o];
    for(re int i=h[u];i+1;i=e[i].nxt)
      {
    re int v=e[i].to;
        if(dis[u]+j-dis[v]+e[i].w>=0&&dis[u]+j-dis[v]+e[i].w<=k)
    (f[dis[u]+j-dis[v]+e[i].w][v]+=f[j][u])%=mod;
      }
    }
}
il int Toposort()
{
  queue<int>Q;
  fp(i,1,n) if(!d[i]) Q.push(i);
  while(!Q.empty())
    {
      re int u=Q.front();Q.pop();seq[u]=++top;
      for(re int i=h[u];i+1;i=e[i].nxt)
    if(!e[i].w)
      {
        re int v=e[i].to;
        if(!--d[v]) Q.push(v);
      }
    }
  fp(i,1,n) if(d[i]) return 0;
  return 1;
}
il bool cmp(re int x,re int y){return dis[x]<dis[y]||(dis[x]==dis[y]&&seq[x]<seq[y]);}
int main()
{
  re int T=gi();
  while(T--)
  {
    memset(h,-1,sizeof(h));memset(f,0,sizeof(f));memset(d,0,sizeof(d));
    cnt=0;ans=0;top=0;
    n=gi();m=gi();k=gi();mod=gi();
    fp(i,1,m)
      {
    re int u=gi(),v=gi(),w=gi();
    add(u,v,w);if(!w) ++d[v];
      }
    if(!Toposort()) {puts("-1");continue;}
    Dijstra();
    fp(i,1,n) sta[i]=i;sort(sta+1,sta+1+n,cmp);
    f[0][1]=1;
    Dp();
    fp(i,0,k) (ans+=f[i][n])%=mod;
    printf("%d\n",ans);
  }
  return 0;
}

简洁的正解

想想上面的转移顺序都是些什么鬼。

由 $j$ 小的转移到 $j$ 大的
由 $dis$ 小的转移到 $dis$ 大的
由拓扑序小的转移到拓扑序大的

注意到这个玩意其实很像由起点向终点转移。但是不可行的原因是有后效性。
想想拓扑排序，只要没有入度就没有后效性。
所以我们要在处理一个点的信息前把其前驱的点的信息处理完。

这里不是 $DAG$ ，不能拓扑排序，怎么办呢？
可以倒着记忆化搜索，这样就能在前驱的信息算完后再算自己的信息。
这样三个条件都满足。。。
状态中只要有当前位置、 $k$ 值就是对的。
有 $0$ 环的情况就是搜一个点的前驱时搜到了自己，记个 $vis$ 判一下即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define pi pair<int,int>
#define mk make_pair
#define fi first
#define se second
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=2e5+100;
int f[55][N],n,m,K,mod,h[N],cnt=1,dis[N],ans;
bool vis[N],use[55][N];
struct Edge{int to,nxt,w;}e[N<<1];
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Dijstra()
{
  priority_queue<pi,vector<pi>,greater<pi> >Q;
  fp(i,1,n) dis[i]=1e9,vis[i]=0;
  dis[1]=0;Q.push(mk(0,1));
  while(!Q.empty())
    {
      re int u=Q.top().se;Q.pop();
      vis[u]=1;
      for(re int i=h[u];i+1;i=e[i].nxt)
    if(!(i&1))
      {
        re int v=e[i].to;
        if(dis[v]>dis[u]+e[i].w)
    {
      dis[v]=dis[u]+e[i].w;
      Q.push(mk(dis[v],v));
    }
      }
      while(!Q.empty()&&vis[Q.top().se]) Q.pop();
    }
}
il int dfs(re int k,re int u)
{
  if(k<0||k>K) return 0;
  if(use[k][u]) return use[k][u]=0,-1;
  if(~f[k][u]) return f[k][u];
  use[k][u]=1;
  re int s=0;
  for(re int i=h[u];i+1;i=e[i].nxt)
    if(i&1)
    {
      re int v=e[i].to;
      re int x=dfs(dis[u]+k-e[i].w-dis[v],v);
      if(x==-1) return use[k][u]=0,-1;
      (s+=x)%=mod;
    }
  use[k][u]=0;
  if(u==1&&k==0) (++s)%=mod;
  return f[k][u]=s;
}
il int work()
{
  fp(i,0,K)
    {
      re int x=dfs(i,n);
      if(x==-1) return -1;
      (ans+=x)%=mod;
    }
  return ans;
}
int main()
{
  re int T=gi();
  while(T--)
  {
    memset(h,-1,sizeof(h));memset(f,-1,sizeof(f));
    cnt=1;ans=0;
    n=gi();m=gi();K=gi();mod=gi();
    fp(i,1,m)
      {
        re int u=gi(),v=gi(),w=gi();
        add(u,v,w);add(v,u,w);
      }
    Dijstra();
    printf("%d\n",work());
  }
  return 0;
}

noip2017逛公园

题面

解析

30pts算法

70pts算法

100pts算法

简洁的正解

内容目录

$30pts$ 算法

$70pts$ 算法

$100pts$ 算法