[关闭]
@ysner 2018-11-03T07:52:19.000000Z 字数 6522 阅读 1982

noip2017逛公园

图论 拓扑排序 DP 最短路


题面

无人不知,无人不晓。

解析

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

算法

最短路计数?跑的同时,顺便算下方案数就好。
于是设表示由点的方案数。

  1. #define pi pair<int,int>
  2. #define mk make_pair
  3. #define fi first
  4. #define se second
  5. priority_queue<pi,vector<pi>,greater<pi> >Q;
  6. il void Dijstra()
  7. {
  8. fp(i,1,n) dis[i]=1e9,vis[i]=0;
  9. dis[1]=0;Q.push(mk(0,1));
  10. while(!Q.empty())
  11. {
  12. re int u=Q.top().se;Q.pop();
  13. vis[u]=1;
  14. for(re int i=h[u];i+1;i=e[i].nxt)
  15. {
  16. re int v=e[i].to;
  17. if(dis[v]>dis[u]+e[i].w)
  18. {
  19. dis[v]=dis[u]+e[i].w;f[v]=f[u];
  20. Q.push(mk(dis[v],v));
  21. }
  22. else if(dis[v]==dis[u]+e[i].w) (f[v]+=f[u])%=mod;
  23. }
  24. while(!Q.empty()&&vis[Q.top().se]) Q.pop();
  25. }
  26. }

算法

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

显然转移式为

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

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

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

于是就有了。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define pi pair<int,int>
  12. #define mk make_pair
  13. #define fi first
  14. #define se second
  15. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  16. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  17. using namespace std;
  18. const int N=1e5+100;
  19. int f[55][N],n,m,k,mod,h[N],cnt,dis[N],ans,sta[N];
  20. bool vis[N];
  21. struct Edge{int to,nxt,w;}e[N<<1];
  22. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
  23. il int gi()
  24. {
  25. re int x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il void Dijstra()
  33. {
  34. priority_queue<pi,vector<pi>,greater<pi> >Q;
  35. fp(i,1,n) dis[i]=1e9,vis[i]=0;
  36. dis[1]=0;Q.push(mk(0,1));
  37. while(!Q.empty())
  38. {
  39. re int u=Q.top().se;Q.pop();
  40. vis[u]=1;
  41. for(re int i=h[u];i+1;i=e[i].nxt)
  42. {
  43. re int v=e[i].to;
  44. if(dis[v]>dis[u]+e[i].w)
  45. {
  46. dis[v]=dis[u]+e[i].w;
  47. Q.push(mk(dis[v],v));
  48. }
  49. }
  50. while(!Q.empty()&&vis[Q.top().se]) Q.pop();
  51. }
  52. }
  53. il void Dp()
  54. {
  55. fp(j,0,k)
  56. fp(o,1,n)
  57. {
  58. re int u=sta[o];
  59. for(re int i=h[u];i+1;i=e[i].nxt)
  60. {
  61. re int v=e[i].to;
  62. if(dis[u]+j-dis[v]+e[i].w>=0&&dis[u]+j-dis[v]+e[i].w<=k)
  63. (f[dis[u]+j-dis[v]+e[i].w][v]+=f[j][u])%=mod;
  64. }
  65. }
  66. }
  67. il bool cmp(re int x,re int y){return dis[x]<dis[y];}
  68. int main()
  69. {
  70. re int T=gi();
  71. while(T--)
  72. {
  73. memset(h,-1,sizeof(h));memset(f,0,sizeof(f));cnt=0;ans=0;
  74. n=gi();m=gi();k=gi();mod=gi();
  75. fp(i,1,m)
  76. {
  77. re int u=gi(),v=gi(),w=gi();
  78. add(u,v,w);
  79. }
  80. Dijstra();
  81. fp(i,1,n) sta[i]=i;sort(sta+1,sta+1+n,cmp);
  82. f[0][1]=1;
  83. Dp();
  84. fp(i,0,k) (ans+=f[i][n])%=mod;
  85. printf("%d\n",ans);
  86. }
  87. return 0;
  88. }

算法

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

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

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define pi pair<int,int>
  12. #define mk make_pair
  13. #define fi first
  14. #define se second
  15. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  16. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  17. using namespace std;
  18. const int N=1e5+100;
  19. int f[55][N],n,m,k,mod,h[N],cnt,dis[N],ans,sta[N],d[N],seq[N],top;
  20. bool vis[N],lab[N];
  21. struct Edge{int to,nxt,w;}e[N<<1];
  22. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
  23. il int gi()
  24. {
  25. re int x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il void Dijstra()
  33. {
  34. priority_queue<pi,vector<pi>,greater<pi> >Q;
  35. fp(i,1,n) dis[i]=1e9,vis[i]=0;
  36. dis[1]=0;Q.push(mk(0,1));
  37. while(!Q.empty())
  38. {
  39. re int u=Q.top().se;Q.pop();
  40. vis[u]=1;
  41. for(re int i=h[u];i+1;i=e[i].nxt)
  42. {
  43. re int v=e[i].to;
  44. if(dis[v]>dis[u]+e[i].w)
  45. {
  46. dis[v]=dis[u]+e[i].w;
  47. Q.push(mk(dis[v],v));
  48. }
  49. }
  50. while(!Q.empty()&&vis[Q.top().se]) Q.pop();
  51. }
  52. }
  53. il void Dp()
  54. {
  55. fp(j,0,k)
  56. fp(o,1,n)
  57. {
  58. re int u=sta[o];
  59. for(re int i=h[u];i+1;i=e[i].nxt)
  60. {
  61. re int v=e[i].to;
  62. if(dis[u]+j-dis[v]+e[i].w>=0&&dis[u]+j-dis[v]+e[i].w<=k)
  63. (f[dis[u]+j-dis[v]+e[i].w][v]+=f[j][u])%=mod;
  64. }
  65. }
  66. }
  67. il int Toposort()
  68. {
  69. queue<int>Q;
  70. fp(i,1,n) if(!d[i]) Q.push(i);
  71. while(!Q.empty())
  72. {
  73. re int u=Q.front();Q.pop();seq[u]=++top;
  74. for(re int i=h[u];i+1;i=e[i].nxt)
  75. if(!e[i].w)
  76. {
  77. re int v=e[i].to;
  78. if(!--d[v]) Q.push(v);
  79. }
  80. }
  81. fp(i,1,n) if(d[i]) return 0;
  82. return 1;
  83. }
  84. il bool cmp(re int x,re int y){return dis[x]<dis[y]||(dis[x]==dis[y]&&seq[x]<seq[y]);}
  85. int main()
  86. {
  87. re int T=gi();
  88. while(T--)
  89. {
  90. memset(h,-1,sizeof(h));memset(f,0,sizeof(f));memset(d,0,sizeof(d));
  91. cnt=0;ans=0;top=0;
  92. n=gi();m=gi();k=gi();mod=gi();
  93. fp(i,1,m)
  94. {
  95. re int u=gi(),v=gi(),w=gi();
  96. add(u,v,w);if(!w) ++d[v];
  97. }
  98. if(!Toposort()) {puts("-1");continue;}
  99. Dijstra();
  100. fp(i,1,n) sta[i]=i;sort(sta+1,sta+1+n,cmp);
  101. f[0][1]=1;
  102. Dp();
  103. fp(i,0,k) (ans+=f[i][n])%=mod;
  104. printf("%d\n",ans);
  105. }
  106. return 0;
  107. }

简洁的正解

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

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

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

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define pi pair<int,int>
  12. #define mk make_pair
  13. #define fi first
  14. #define se second
  15. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  16. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  17. using namespace std;
  18. const int N=2e5+100;
  19. int f[55][N],n,m,K,mod,h[N],cnt=1,dis[N],ans;
  20. bool vis[N],use[55][N];
  21. struct Edge{int to,nxt,w;}e[N<<1];
  22. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
  23. il int gi()
  24. {
  25. re int x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il void Dijstra()
  33. {
  34. priority_queue<pi,vector<pi>,greater<pi> >Q;
  35. fp(i,1,n) dis[i]=1e9,vis[i]=0;
  36. dis[1]=0;Q.push(mk(0,1));
  37. while(!Q.empty())
  38. {
  39. re int u=Q.top().se;Q.pop();
  40. vis[u]=1;
  41. for(re int i=h[u];i+1;i=e[i].nxt)
  42. if(!(i&1))
  43. {
  44. re int v=e[i].to;
  45. if(dis[v]>dis[u]+e[i].w)
  46. {
  47. dis[v]=dis[u]+e[i].w;
  48. Q.push(mk(dis[v],v));
  49. }
  50. }
  51. while(!Q.empty()&&vis[Q.top().se]) Q.pop();
  52. }
  53. }
  54. il int dfs(re int k,re int u)
  55. {
  56. if(k<0||k>K) return 0;
  57. if(use[k][u]) return use[k][u]=0,-1;
  58. if(~f[k][u]) return f[k][u];
  59. use[k][u]=1;
  60. re int s=0;
  61. for(re int i=h[u];i+1;i=e[i].nxt)
  62. if(i&1)
  63. {
  64. re int v=e[i].to;
  65. re int x=dfs(dis[u]+k-e[i].w-dis[v],v);
  66. if(x==-1) return use[k][u]=0,-1;
  67. (s+=x)%=mod;
  68. }
  69. use[k][u]=0;
  70. if(u==1&&k==0) (++s)%=mod;
  71. return f[k][u]=s;
  72. }
  73. il int work()
  74. {
  75. fp(i,0,K)
  76. {
  77. re int x=dfs(i,n);
  78. if(x==-1) return -1;
  79. (ans+=x)%=mod;
  80. }
  81. return ans;
  82. }
  83. int main()
  84. {
  85. re int T=gi();
  86. while(T--)
  87. {
  88. memset(h,-1,sizeof(h));memset(f,-1,sizeof(f));
  89. cnt=1;ans=0;
  90. n=gi();m=gi();K=gi();mod=gi();
  91. fp(i,1,m)
  92. {
  93. re int u=gi(),v=gi(),w=gi();
  94. add(u,v,w);add(v,u,w);
  95. }
  96. Dijstra();
  97. printf("%d\n",work());
  98. }
  99. return 0;
  100. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注