华师一附中OI组

标题: NOIP2017 逛公园 洛谷3953（Day1 T3） [打印本页]
作者: WWX    时间: 2018-6-5 20:06
标题: NOIP2017 逛公园 洛谷3953（Day1 T3）
本帖最后由 WWX 于 2018-6-5 20:07 编辑

https://www.luogu.org/problemnew/show/P3953
题目很长，就不贴了
此题值得仔细思考，品味。
在写这题之前，建议先完成路径统计洛谷1068（https://www.luogu.org/problemnew/show/P1608）以及最短路计数洛谷1144（https://www.luogu.org/problemnew/show/P1144）
我们发现k的范围只有50，所以可以考虑用dp来解决这个问题
我们用dp[j]表示到节点i的长度为dis+j的路径条数dis为到节点i的最短距离
然后就可以写出转移方程dp[j]+=dp[k][j-(dis[j]-dis[k]+dis[j])]k为所用可以到达i的节点
在考虑什么时候会有无数条路径，显然是当图存在0环的时候
我们打一个标记在统计时判断一下，就好了
由于不太好推，我们利用记忆化搜索来实现代码
作者: WWX    时间: 2018-6-5 20:08
  1. # include<algorithm>
  2. # include<iostream>
  3. # include<cstring>
  4. # include<cstdio>
  5. # include<queue>
  6. const int  mn  = 100010;
  7. const int  maxn  =  200010;
  8. inline int read()
  9. {
  10.     int x=0;
  11.     char ch=getchar();
  12.     while(ch<'0'||ch>'9') ch=getchar();
  13.     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  14.     return x;
  15. }
  16. using namespace std;
  17. int t,n,m,K,p,ans,edge_max;
  18. int dp[mn][51],mark[mn][51];
  19. int dis[mn],head1[mn],head2[mn];
  20. bool flag;
  21. bool vis[mn];
  22. queue<int> q;
  23. struct edge{int to,dis,next;}e1[maxn],e2[maxn];
  24. void add(int x,int y,int z)
  25. {
  26.     e1[++edge_max].to=y;
  27.     e1[edge_max].dis=z;
  28.     e1[edge_max].next=head1[x];
  29.     head1[x]=edge_max;
  30.     e2[edge_max].to=x;
  31.     e2[edge_max].dis=z;
  32.     e2[edge_max].next=head2[y];
  33.     head2[y]=edge_max;
  34. }
  35. void pre()
  36. {
  37.     dis[1]=0;
  38.     q.push(1);
  39.     while(!q.empty())
  40.     {
  41.         int u=q.front();
  42.         q.pop();
  43.         vis[u]=0;
  44.         for(int i=head1[u];i;i=e1[i].next)
  45.         {
  46.             if(dis[u]+e1[i].dis<dis[e1[i].to])
  47.             {
  48.                 dis[e1[i].to]=dis[u]+e1[i].dis;
  49.                 if(!vis[e1[i].to])
  50.                 {
  51.                     vis[e1[i].to]=1;
  52.                     q.push(e1[i].to);
  53.                 }
  54.             }
  55.         }
  56.     }
  57. }
  58. int dfs(int x,int k)
  59. {
  60.     if(flag)
  61.         return 0;
  62.     if(mark[x][k]==1)//如果有0环，路径则有无数条
  63.     {
  64.         flag=true;
  65.         return 0;
  66.     }
  67.     if(mark[x][k]==2)
  68.         return dp[x][k];
  69.     mark[x][k]=1;
  70.     for(int i=head2[x];i;i=e2[i].next)
  71.     {
  72.         int u=e2[i].to,len=e2[i].dis;
  73.         if(dis[u]+len>dis[x]+k)
  74.             continue;
  75.         dp[x][k]+=dfs(u,k-(dis[u]+len-dis[x]));
  76.         if(flag) return 0;
  77.         dp[x][k]%=p;
  78.     }
  79.     mark[x][k]=2;
  80.     return dp[x][k];
  81. }
  82. int main()
  83. {
  84.     int x,y,z;
  85.     t=read();
  86.     while(t--)
  87.     {
  88.         ans=0;
  89.         flag=false;
  90.         memset(dis,0xf,sizeof(dis));
  91.         memset(head1,0,sizeof(head1));
  92.         memset(head2,0,sizeof(head2));
  93.         memset(dp,0,sizeof(dp));
  94.         memset(mark,0,sizeof(mark));
  95.         edge_max=0;
  96.         n=read(),m=read(),K=read(),p=read();
  97.         for(int i=1;i<=m;i++)
  98.         {
  99.             x=read(),y=read(),z=read();
  100.             add(x,y,z);
  101.         }
  102.         pre();
  103.         dp[1][0]=1;
  104.         for(int i=0;i<=K;i++)
  105.         {
  106.             ans+=dfs(n,i);
  107.             //printf("%d\n",ans);
  108.             ans%=p;
  109.         }
  110.         if(flag)
  111.             puts("-1");
  112.         else printf("%d\n",ans);
  113.     }
  114.     return 0;
  115. }
复制代码
作者: 胡雨菲菲    时间: 2018-6-7 14:42
太强了！%%%



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2