post_img

SSL 2603_最小路径覆盖问题_网络流

摘要

题目大意 给出一个图,求出最小路径覆盖 思路 最小路径覆盖=总点数-最大匹配 用全部点建一个二分图然后跑一遍最大流,记录下每一个点 …

post_img

洛谷 1073_最优贸易_spfa+dfs

摘要

题目描述 C 国有 n 个大城市和 m 条道路,每条道路连接这 n 个城市中的某两个城市。任意两个 城市之间最多只有一条道路直接相 …

post_img

洛谷 2296_寻找道路_spfa+dfs

摘要

题目描述 在有向图G 中,每条边的长度均为1 ,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件: 1 . …

post_img

洛谷 1346_电车_spfa

摘要

题目描述 在一个神奇的小镇上有着一个特别的电车网络,它由一些路口和轨道组成,每个路口都连接着若干个轨道,每个轨道都通向一个路口(不 …

post_img

洛谷 3371_单源最短路径_spfa

摘要

题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度 思路 一个普通的spfa 然后注意的是题目中给定了最大值 …

post_img

洛谷 1144_最短路计数_spfa

摘要

题目描述 给出一个N个顶点M条边的无向无权图,顶点编号为1~N。问从顶点1开始,到其他每个点的最短路有几条。 思路 因为是无权边, …

post_img

洛谷 1629_邮递员送信_Dijkstra

摘要

题目描述 有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的 …