首页 > 其他分享 >[SCOI2012] 滑雪

[SCOI2012] 滑雪

时间:2023-11-23 17:11:16浏览次数:37  
标签:最小 生成 外向 回溯 滑雪 SCOI2012

Description

给定一个带边权有向图。现在从点 \(1\) 开始走,走的过程中可以无代价回溯任意多步,求在经过最多点的情况下(重复的点算一次),最小边权和是多少。

Solution

先从点 \(1\) BFS,能走到的点就是第一小问答案。根据回溯条件,在最优答案中,每条边至多走一次(考虑走两次的话,一定有一次是不必要的,可以通过调整回溯策略来消去)。以及走过的边不会形成环,否则可以通过在形成环的那一步通过回溯操作到达相同的点,且没有花费。所以所有所经过的路径的集合构成一棵外向树。于是问题就转换为了,求原图的一棵以点 \(1\) 为根的外向最小生成树。

和无向图的最小生成树求法有些许差别,该外向最小生成树需要保证除根以外的每个点都至少有一条入边,即有父亲。所以考虑用堆优化的 Prim ,从 \(1\) 开始扩展,每次新加入一个点,就把该点所有出边加到堆里面,每次取最小的边加入生成树,复杂度 \(O(n\log m)\)。

标签:最小,生成,外向,回溯,滑雪,SCOI2012
From: https://www.cnblogs.com/wwlwQWQ/p/17852024.html

相关文章

  • 基于Python+Pygame实现一个滑雪小游戏
    目录项目介绍Pygame介绍项目文件夹介绍演示视频代码免费领取一、项目介绍使用介绍:运行main.py文件后,通过左右按键可以控制小人的移动,如果经过旗杆那么+10分,如果碰到树木那么减50分。二、Pygame介绍Pygame是一个用于游戏开发和多媒体应用的Python库。它是基于SDL(Simple......
  • P2573 [SCOI2012] 滑雪
    P2573bzoj#2753一开始以为最优答案就是最短路径树,结果发现是错的首先我们可以观察一下,发现时间胶囊的作用就是回到某个已经经过的节点,显然是一个最小生成树但是这道题还有高度的限制,我们在生成树的时候并不能把所有的边直接按照边权排序,因为这样的话可能会出现一些不合法的边......
  • 雾里滑雪笔记(三)热力学第一定律
    热一律及其衍生物一、热力学第一定律的基本内容热力学第一定律是能量守恒定律在一定条件下的表现形式。为了理解这种说法,我们考虑所有可能的形式的能量。系统的总能量可以分为三部分:系统在外力场中的势能或位能$V$,系统整体运动的动能$T$,和系统的内能,即热力学能$U$。$$E=......
  • 滑雪 OJ3651
    这个题我是不会用dp做,众所周知,能用记忆化搜索的题肯定能用dp,能用dp的不一定用记忆化搜索.这个题正好用记忆化搜索可以过,欸嘿#include<bits/stdc++.h>usingnamespacestd;constintN=2020;intf[N][N],a[N][N],n,m,res;//a数组存储状态,f数组存储每条路最大的值intdx......
  • AcWing901. 滑雪(python)
    题目详情知识点记忆化DP思路自己的思路(仅参考):一开始想的是找最大值,然后从最大值开始向下滑,但是我们是要求最长路径,不一定是从最高的点滑下去的,也不一定是滑到最低点,而且会存在最大值不止一个的情况,所以我们应该是针对每一个点,都求出当前该点出发能去的最长路径,然后求完之后......
  • 2023年中国传媒大学程序设计大赛 G.跳台滑雪 线段树
    传送门#include<iostream>#include<cstring>#include<iomanip>#include<algorithm>#include<stack>#include<queue>#include<numeric>#include<cassert>#......
  • P5842 [SCOI2012]Blinker 的仰慕者 题解
    题意简述:求\([l,r]\)内各个数位积为\(k\)的数的和。解:在看题解前,请先确认自己是否精通了数位dp模板题,否则会很难理解。对于朴素的数位dp,我们可以记录\(f_{i,j......
  • POJ 1088 滑雪 递归+dp | 拓扑排序
    从每个点(i,j)向四个方向去看如果某一个方向(a,b)的数值比当前位置小先求解(a,b)的最长距离,之后加1即可朴素的递归重复求解了很多子问题,我们每计算出一个子问题的解,便......
  • B - 滑雪【2022GDUT寒假集训-简单DP】
    B-滑雪原题链接思路\(定义f(i,j)为从坐标(i,j)出发的最大值\)\(状态转移方程f(i,j)=max(f(i+dx[k],j+dy[k]))\)\(答案为max(f(1,1),f(1,2),...,f(n,m))\)注意......
  • 洛谷 P1434 [SHOI2002] 滑雪
    P1434[SHOI2002]滑雪-洛谷|计算机科学教育新生态(luogu.com.cn)这道题数据很水,可以用记忆化过,这里说一下堆优化+DP的方法 首先是常用的DP逆向思维,也是此题最终......