E - Nearest Black Vertex 题目链接 题意 给你一个n点m边的无向图，每个点需要染成黑色或白色，有k个限制(p_i, d_i)为距离p_i点最近的黑点距离为d_i，求是否存在这样的图，若有多种方案输出任意一种即可。 数据范围：2\le n\le 2000,\ n - 1\le m\le \min\lbrace \frac{n\times (n−1)}{2},2000\rbrace, 0\le k\le n 思路 注释都写在代码上了，这里想写的原因是，如果边权为1的话，可以对每个点进行一次bfs…
题目链接：M. Moving Both Hands 题意 给你一个n点m边的带权有向图，一开始双手放在点1以及其他点，每次可以移动一只手，花费是边权，求两只手到一个点的最短时间。一共有n-1次询问，分别是点1到其他n-1个点的最小花费。 最短时间是：1->2->4 ｜ 4
题目 题目来源于北华大学计算机程序设计算法提高训练营个人赛的J题，邀请码:bhu2022。 给出一个n(1\leq n\leq 10^6)点m边的无向图每条边长为1，每个点拥有一个0/1的点权，0表示雌性，1表示雄性。一共有q次询问，每次询问x，回答距离点x最近的异性的最短距离是。 思路 考虑到数据范围比较大，肯定不能用暴力，所以需要用两遍bfs，一次从所有的0出发，去更新每个1点到0的最短距离；一次从所有的1出发，去更新每个0点到1的最短距离。 令f[i][0/1]，其中f[i][0]表示点i到0的最短距离，f[…
题目 题目来源于大连大学2022年4月程序设计竞赛，我和伍老师合砍12题rk23，差两题ak。 题目链接：F-旅行_大连大学2022年4月程序设计竞赛（同步赛） (nowcoder.com) 一句话题意：给你n点m边的有向图，每条边有边权，点没有点权，q次询问，每次询问点x是否在点1到点n的最短路径上，最短路径可能有多条。 如上图，从1到4的话，最短路当然是"1->3->4"，这三个点都是，而2不是。 思路 我们先用一个二维数组dis[i][j]来表示点i到点j之间的最短距离，那么对于起点是1，终点是n来说，询问一…
简介 二分图又称作二部图，是图论中的一种特殊模型。 最大匹配数 = 最小点覆盖 = 总点数- 最大独立集 = 总点数- 最小路径点覆盖 比如下图： 二分图匹配的话我们可以用到——匈牙利算法，二分图判定的话我们可以直接用BFS，我看有些图是DFS也是一样的道理，就是判断邻边是否颜色相同（重点） 思路 1）我们首先定一个起点，将起点加入队列deque里面，每次bfs取出来顶端的 2）然后对其的所有邻边进行染色（染不同的色） i）情况一：相邻的边没有被染色 那么也就是还没有进入过队列，那么这个时候边染成不同的色，边将其压…
题目 给定一个有向图G和其中的两个结点s,t。询问这两个结点之间存在多少条经过了恰好k条边的道路。 注意：包括重边和自环！ 例如下图 从3到2，长度为5，我们有6条道路,分别是： 1. D,A,B,D,A 2. D,A,B,D,E 3. D,E,B,D,A 4. D,E,B,D,E 5. C,C,C,D,A 6. C,C,C,D,E 思路 这个题一开始我是没思路的，实际上就是一个板子题...只需要学过离散数学... 把邻接矩阵写出来为 然后对其进行K次幂计算（可用矩阵快速幂），得到： 因为起点s=3,终点t=2，所…
题目 题目链接：1471. 牛奶工厂 - AcWing题库 牛奶生意正红红火火！ 农夫约翰的牛奶加工厂内有 N 个加工站，编号为 1…N，以及 N−1 条通道，每条连接某两个加工站。（通道建设很昂贵，所以约翰选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。 为了创新和提升效率，约翰在每条通道上安装了传送带。 不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！ 所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。 然而，约翰认为事情可能还不算完全失败，…
题目链接 1738. 蹄球 - AcWing题库 题意 给出n(1\leq n\leq 100)头牛，每头牛有自己的位置x_i(1\leq x_i\leq 1000)。每头牛给两侧相邻的牛传球，规定是传给距离较小的那个，如果相同则选左边的，每个牛都需要传一次球，你可以一开始在若干个牛上放球，然后开始传，问开始需要放置多少个球使得所有牛都持球一次。 思路 有n个点，每个点传一次（这个是固定的），就是n条边。 n个点，n条边 —— 基环树 所以，这里面是若干个基环树，为什么说若干的，是因为有可能它不连通，所以我们分为两…
