Handwer

分类

算法(1) 题解(4)

/ 注册

全部文章（共5篇）

欧拉图学习笔记

从一个点出发走一走约定 1. 定义表示从的一条边（若无特别说明，即为无向边）2. 定义表示从，经过两条边的路径3. 定义「孤立点」表示一个度为 0 的点4. 定义「奇顶点」表示一个度数为奇数的点5. 定义对于有向图 G ，将所有的有向边替换为无向边得到图 G 的基图，若图 G...

2019-07-19

0 1374

飞行路线

入门级别的分层图最短路题目地址双倍经验前言先介绍一下分层图最短路。分层图最短路是指在可以进行分层图的图上解决最短路问题。一般模型是：在图上，有k次机会可以直接通过一条边，问起点与终点之间的最短路径。题目描述 Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司...

2019-07-19

0 653

炮兵阵地

ProjectDP - 29 需要维护两行状态的状压DP 题目描述司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够...

2019-07-19

0 692

Equipment

ProjectDP - 33 状态压缩 + DFS 题面 PDF 解题思路首先是这个玄学的数据范围（每个组只有5个元素）很容易让人想到状压首先把 k >= 5 的情况特判一下可以选择超过5个组那么显然选择最大的就行了对于每一个组，枚举它的每一种状态对于这个状态，统计一下选择这个...

2019-07-19

0 672

Tree 2

年轻人的第一道国家集训队题目如果我们不做任何处理，直接跑MST（Minimum Spanning Tree，最小生成树），结果会有三种：正好跑出条白边白边多了白边少了第一种情况自然是最好的剩下两种情况如何解决？引起白边少的原因：黑边的边权相对较小，程序贪心地选择了更多...

2019-07-19

0 688