NOIP2017tg【逛公园】 题解
先说点别的
emmm……，这是本蒟蒻的第一篇题解，大佬们勿喷QwQ（要不是看到写题解可以加贡献，我才……）
可以看到标签，是2017年提高的题目，好像是Day1T3，感觉提高考这样的题目挺好的，至少考场上也可以很快想到做法。唉……，我太菜了，调这道题调了一下午才满，要是在考场上肯定死。
看了题解几位奆佬的思路，有拓扑的，记忆化搜索的，跑反图的，感觉和自己想得不是很一样，于是想讲一下本蒟蒻写这道题的思路。
几个好消息
1)此题不卡SPFA！！！请SPFA党放心使用！！！
2)此题部份分给得很足，直接使用P1608路径统计的方法可以过30分。
关于此题
前置技能：
2、dp
题意：应该很清楚了吧，求1至n的所有路径中，小于等于dis[n]+K的路径数，结果取膜P。注意，图有可能会出现0边和0环。
既然我们选择做这道题，就要奔着满分前进！
做法
本蒟蒻选择的做法是SPFA加dp，看很多大佬都要加拓扑什么的来确定dp更新顺序和判0环，不过本蒟蒻表示完全没有必要，其实在跑SPFA的过程中，我们就可以随便把这些问题解决掉。
1、判0环
判0环和判负环其实差不多，只需要在SPFA中加一个判断即可，但是，由于此题卡时间卡得很紧，所以我们机房某大佬教了我卡带，这样判0环听说可以快很多。
if(dis[v]>=dis[u]+cost[i])
注意：SPFA这里需要把'>'改成">=",不然判不了0环
剩下的判0环方法就和判负环差不多,如果还不明白可以看代码。（另外提供一种判0环方式，把0边全部抽出来，然后判环，拓扑什么的）
2、确定dp更新顺序
这个其实也很简单，我们不难发现，其实只有0边两个点的顺序需要确定更新顺序，其他只需要按dis从小到大的顺序更新就可以了。于是我们在SPFA中加一个更新就可以了。
if(id[v]<id[u]+1)id[v]=id[u]+1;
这样即可确定dp更新顺序。dp前先按dis为第一关键字，id为第二关键字排序即可。
3、dp
额……，讲了怎么久的dp更新顺序，可能你们还不懂怎么dp吧，我的dp方法和Kelin大佬的一样，都是f[i][j]表示1至i的路径中，小于等于dis[i]+j的路径数。
转移也很简单，只要(dis[u]+j+(u至v的长度)-dis[v]<=K)
那么就将f[v][dis[u]+j+(u至v的长度)-dis[v]]+=f[u][j];
最后记得取膜蛤！dp的更新顺序记得按关键字排序啊。
还有，本蒟蒻由于dp学得不是很好，所以讲得如果不懂的话，可以看代码或者Kelin大佬讲的，我觉得他dp讲得比我好啊QAQ。
for(int k=0;k<=kk;k++) //dp
{
for(int j=1;j<=n;j++)
{
int u=a[j].pos,d=dis[u];
if(d>=inf)continue; //小剪枝
for(int i=head[u];i!=-1;i=Next[i])
{
int v=to[i];
if(cost[i]-dis[v]+d+k<=kk) //如果当前到v的状态的花费小于kk就更新
{
f[v][cost[i]-dis[v]+d+k]+=f[u][k]; //更新
f[v][cost[i]-dis[v]+d+k]%=mod; //记得取mod
}
}
}
}
dp代码如上，还是比较好想到的呢。
好了那么思路也就差不多了，总体的难度其实不是很大，不过这样写的时间复杂度会比用拓扑的高，毕竟在找0环的时候比较耗时间，但是方法肯定是没问题的，接下来来看全部代码吧。
AC代码：
#include<bits/stdc++.h>
#define maxm 800000
#define maxn 400000
#define inf 20010100
using namespace std;
int cnt,from[maxm],to[maxm],cost[maxm],Next[maxm],head[maxm],cont[maxm],cb[maxn],id[maxn];//嗯，定义有点丑蛤
int dis[maxn],vis[maxn],f[maxn][65],ans;
int n,m,x,y,z,mod,kk;
struct kkk{
int dis,id,pos;
}a[maxn];
queue<int>q;
int cmp(kkk a,kkk b){ //排序操作
if(a.dis==b.dis)return a.id<b.id; //记得以dis为第一关键字哦~~~,id为第二关键字
else return a.dis<b.dis;
}
bool SPFA(int S){ //SPFA求最短路
while(!q.empty())q.pop();
for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0,id[i]=0;
vis[S]=1;q.push(S);dis[S]=0;
int sum=0; //上面为初始化
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=0;
sum+=cb[u]+1;if(sum>2000000)return false; //卡带判0环
for(int i=head[u];i!=-1;i=Next[i])
{
int v=to[i];
if(dis[v]>=dis[u]+cost[i])
{
if(++cont[v]>=n)return false; //当然普通判0环也少不了
dis[v]=dis[u]+cost[i];
if(id[v]<id[u]+1)id[v]=id[u]+1; //id确定0边两个端点的更新顺序
if(vis[v]==0)
{
vis[v]=1;
q.push(v);
}
}
}
}
return true;
}
void add(int x,int y,int z){ //建边
cnt++;
cost[cnt]=z;cb[x]++;
from[cnt]=x;to[cnt]=y;
Next[cnt]=head[x];head[x]=cnt;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(head,-1,sizeof(head)); //初始化{
memset(cont,0,sizeof(cont));ans=0;
memset(a,0,sizeof(a));cnt=0; //}初始化
scanf("%d%d%d%d",&n,&m,&kk,&mod); //输入{
for(int i=1;i<=m;i++)
scanf("%d%d%d",&x,&y,&z),add(x,y,z);//}输入
bool flag=SPFA(1); //SPFA跑最短路
if(flag==false) //随便判0环
{printf("-1\n");continue;}
//***********************以上为基本操作-分界线-以下为dp求解***********************
for(int i=1;i<=n;i++)a[i].pos=i,a[i].dis=dis[i],a[i].id=id[i]; //dp的初始化
sort(a+1,a+n+1,cmp); //进行排序
//f[i][j]表示1至i的路径中，小于等于dis[i]+j的路径数
memset(f,0,sizeof(f));f[1][0]=1;//dp初始化
for(int k=0;k<=kk;k++) //dp
{
for(int j=1;j<=n;j++)
{
int u=a[j].pos,d=dis[u];
if(d>=inf)continue; //小剪枝
for(int i=head[u];i!=-1;i=Next[i])
{
int v=to[i];
if(cost[i]-dis[v]+d+k<=kk) //如果当前到v的状态的花费小于kk就更新
{
f[v][cost[i]-dis[v]+d+k]+=f[u][k]; //更新
f[v][cost[i]-dis[v]+d+k]%=mod; //记得取mod
}
}
}
}
for(int i=0;i<=kk;i++)
ans+=f[n][i],ans%=mod; //最后统计答案
printf("%d\n",ans);
}
}
最新文章
- em与px换算关系以及常用列表
- [译]libev和libevent的设计差异
- 安装完Pydev却无法创建Python工程
- 跟我一起学WCF(6)——深入解析服务契约[下篇]
- Teradata（不同date输出要求；表类型）
- EasyUI_tree根据数据库数据生成树形结构JSON格式
- SAP BW 通过视图创建数据源(无单位)
- python(5)–sys模块
- centos7 rabbitmq系统部署
- 为什么app都是异步编程
- Spring连接MySQL、Oracle和SQL Server的数据库运动连接属性
- yield语句
- Next Greater Element I
- 阶段小项目2：显示bin格式图片
- 搜索引擎solr和elasticsearch
- 关于table表格 td里内容较多换行的处理方法
- hdu1814 Peaceful Commission
- Windows10用fiddler抓包Android应用（解决手机设置代理后无法上网，设置只抓app包）
- java对excel操作
- Golang安装与环境的配置