ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

GPLT天梯赛2022真题 L2-3 龙龙送外卖 (25 分)(图论 + 记忆化搜索)

2022年4月25日 1191点热度 1人点赞 0条评论

本题没有传送门,就把题目写清楚吧。

碎碎念

在考场上这道题没想出来,真是寄了。一直在想LCA,然后想dfs,最短路。后面想利用树的性质,怎么都想不出。

思路

先考虑每个点都要走一次且回到起点的情况,那就是每个点往上走,每条边都要走两次。这个可以类比dfs的过程,每条边都要走到两次才能保证回到起点。

由于本题要求无需回到起点,所以用路程减去一个最大深度(最长的一条链)就是答案。

我自己画的图

比如这个图,我要从起点1去 3 5 8 9送外卖,就可以选择以8或者9为终点,那么就是每个点往上走直到“会经过的点”的边的数量 * 2 - 最长的链,这就是答案。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 2e5 + 9;

int fa[maxn],dep[maxn];
bitset<maxn> vis;//用于标记某点是否走过 

int d(int x)//记忆化搜索 
{
	if(fa[x] == -1)return 0;
	else if(dep[x])return dep[x];
	return dep[x] = d(fa[x]) + 1;
}

signed main()
{
	int N, M;cin >> N >> M;
	for(int i = 1;i <= N; ++ i)
	{
		int x;scanf("%lld", &x);
		fa[i] = x;
	}
	for(int i = 1;i <= N; ++ i)dep[i] = d(i);//获取每个点的深度 
	
	int ans = 0, maxd = 0;//maxd记录最大深度 
	while(M --)
	{
		int x;scanf("%lld", &x);
		maxd = max(maxd, dep[x]);//更新最大深度
		 
		while(fa[x] != -1 && !vis[x]) //从x点向上直到 根 或 已经走过的点 
		{
			vis[x] = 1;
			x = fa[x];
			ans += 2;
		}
		
		printf("%lld\n",ans - maxd);//输出答案 
	}
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ gplt 团体程序设计天梯赛 图论 树 算法竞赛 记忆化搜索
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 碎碎念
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号