发布于2024-10-08
信息学竞赛模板（十九）——二分图
如果一张无向图的 $N(N>2)$ 个节点可以分成 $A,B$ 两个非空集合，其中 $A\cap B = \emptyset$，并且在同一集合内的点之间都没有相连的边，那么称这张图为一张**二分图**
发布于2022-03-23
2019年第十届蓝桥杯省赛-E.迷宫
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。 迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按 `DRRURRDDDR` 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于更复杂的迷宫，请找出字典序最小的一个最短路径为答案。
发布于2021-12-16
2015年第六届蓝桥杯省赛-J. 生命之树
在 X 森林里，上帝创建了生命之树。 他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。 上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 {a, v1, v2, ..., vk, b} 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。 在这个前提下，上帝要使得 S 中的点所对应的整数的和尽
发布于2021-11-24
AcWing第4场周赛 — C. 构造有向无环图
给定一个由 n 个点和 m 条边构成的图。 不保证 给定的图是连通的。 图中的一部分边的方向已经确定，你不能改变它们的方向。 剩下的边还未确定方向，你需要为 每一条 还未确定方向的边指定方向。 你需要保证在确定所有边的方向后，生成的图是一个有向无环图。