【蓝桥杯冲冲冲】旅行计划

蓝桥杯备赛 | 洛谷做题打卡day18

旅行计划

题目描述

Kira酱要去一个国家旅游。这个国家有 $N$ 个城市，编号为 $1$ 至 $N$，并且有 $M$ 条道路连接着，Kira准备从其中一个城市出发，并只往东走到城市 $i$ 停止。

所以她就需要选择最先到达的城市，并制定一条路线以城市 $i$ 为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。

现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的 $i$，都需要你为Kira酱制定一条路线，并求出以城市 $i$ 为终点最多能够游览多少个城市。

输入格式

第一行为两个正整数 $N,M$。

接下来 $M$ 行，每行两个正整数 $x,y$，表示了有一条连接城市 $x$ 与城市 $y$ 的道路，保证了城市 $x$ 在城市 $y$ 西面。

输出格式

$N$ 行，第 $i$ 行包含一个正整数，表示以第 $i$ 个城市为终点最多能游览多少个城市。

样例 #1

样例输入 #1

5 6
1 2
1 3
2 3
2 4
3 4
2 5

样例输出 #1

1
2
3
4
3

提示

均选择从城市 $1$ 出发可以得到以上答案。

• 对于 $20\%$ 的数据，$1\le N\le 100$；
• 对于 $60\%$ 的数据，$1\le N\le 1000$；
• 对于 $100\%$ 的数据，$1\le N\le 100000$，$1\le M\le 200000$。

题解代码

学会利用新知，自己多试试并尝试积攒一些固定解答方案，debug，以下是题解代码 ~

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath> //别忘记头文件哦
using namespace std;
int n,m,lin[100010],in[100010],total,f[100010];
queue<int>q;
struct cym{
	int to,next;
}e[400010];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		e[++total].to=y;
		e[total].next=lin[x];
		lin[x]=total;
		in[y]++;
	}
	for(int i=1;i<=n;i++)
	if(in[i]==0)
	{
		f[i]=1;
		q.push(i);
	}
	while(!q.empty())
	{
		int cnt=q.front();q.pop();
		for(int i=lin[cnt];i;i=e[i].next)
		{
			f[e[i].to]=max(f[e[i].to],f[cnt]+1);
			if(--in[e[i].to]==0)q.push(e[i].to);	
		}	
	}
	for(int i=1;i<=n;i++)printf("%d\n",f[i]);
}

我的一些话

• 今天来巩固动态规划dp，很显然，每个点的答案是它所有前驱节点的答案加1，即f[i]=max(f[i],f[j]+1); 考虑空间复杂度用邻接表存图，在拓扑排序同时DP就好了不用再外面再做什么工作。多思考思路还是很好掌握的，虽然一次性AC有一定难度，需要通盘的考虑和理解，以及扎实的数据结构基础才能独立写出AC代码。但无论难易，大家都要持续做题，保持题感喔！一起坚持(o´ω`o)

• 如果有非计算机专业的uu自学的话，关于数据结构的网课推荐看b站上青岛大学王卓老师的课，讲的很细致，有不懂都可以私信我喔

• 总结来说思路很重要，多想想，多在草稿纸上画画，用测试数据多调试，debug后成功编译并运行出正确结果真的会感到很幸福！

• 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

• 不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）