L2-044 大众情人「最短路」
L2044 大众情人https://pintia.cn/problemsets/994805046380707840/exam/problems/1518582589840875520 题目描述： n个人，有向图，有男女性别之分，我们定义异
「图论」判环、求环、最小环
判断是否存在环 无向图 并查集不仅能判环，还能判奇环，即利用带权并查集 dfs标记法 SPFA（给边加权值的方法来通过判正负环进行判环） Tarjan锁点，如果存在双联通分量则存在环 有向图 dfs标记法，用fa数组来记录 拓扑排序，跑完拓
严格次小生成树
次小生成树 即不等于最小生成树的生成树的值的最小值 方法是考虑每条不在最小生成树上的边，连上这条边以后会在树上形成一个环，我们需要在这个环上找一个不等于刚连起来的边的最大值，然后删掉它 这里用的是倍增LCA来维护树上链的最大值和次大值 我们
电力「点双连通数量、无向图缩点」
电力https://www.acwing.com/problem/content/1185/ 题目描述： 给定一个由 n 个点 m 条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少。 思路： 对于一个连通图，肯定是删除图内割点
矿场搭建「点双连通分量、无向图缩点」
矿场搭建https://www.acwing.com/problem/content/398/ 题目描述： 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。 为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。 于
AtCoder Beginner Contest 244 E - King Bombee 「图论 + dp」
E King Bombeehttps://atcoder.jp/contests/abc244/tasks/abc244e 题目描述： n个点，m条边，求起点是s，终点是t，经过偶数次点x的长度为k+1的路径的数量 思路： dpijk表示从
观光奶牛 「二分答案 + SPFA判负环」
观光奶牛https://www.acwing.com/problem/content/363/ 题目描述： n个点，m条边，每个点都有一个权值fi,每条边都有一个权值vali,求图中的一个环，使的环上“各个点的权值之和”除以“环上个各个边的
「kuangbin带你飞」专题四最短路专题题解
Til the Cows Come Homehttps://vjudge.net/problem/POJ2387 板子题 Froggerhttps://vjudge.net/problem/POJ2253 求所有1到n的路径中价值最大的边的
通信线路「分层图最短路」||「二分答案 + 巧妙的建图跑最短路」
通信线路https://www.acwing.com/problem/content/342/ 题目描述： n个点，m条双向边，求1到n的路程中价格第k+1大的边的权值最小是多少，如果路径数量小于k+1，则输出0 思路1:分层图最短路 求第
排序「floyed求传递闭包」
排序https://www.acwing.com/problem/content/description/345/ 题目描述： 给定 n 个变量和 m 个不等式。其中 n 小于等于 26，变量分别用前 n 的大写英文字母表示。 不等式之间具
拯救大兵瑞恩「bitset状态压缩 + BFS」
拯救大兵瑞恩https://www.acwing.com/problem/content/1133/ 题目描述： n \ m的地图，有p类门，当然对应的就有p类钥匙可以开对应的门，拿到对应门的钥匙才能开对应的门，门是双开门，还有若干个不可逾
负权图的最短路计数
最短路计数https://www.acwing.com/problem/content/1136/ 题目描述： n个点m条边的无向无权图，问从顶点1开始，到其他每个点的最短路有几条 思路： 最短路计数首先要满足的条件是不能存在权值为0的环，
道路与航线「缩点 + 拓扑排序 + 迪杰斯特拉」
道路与航线https://www.acwing.com/problem/content/description/344/ 题目描述： n个点，R条双向边，P条单向边，双向边的权值都是正的，单向边的权值有正有负，给你一个起点，问起点到每个点的
F - False God「思维」「图论」「树上最长路」
F False Godhttps://vjudge.csgrandeur.cn/problem/Gym102803F 题目描述： 你有一个金将，对面有n个步兵，金将每回合可以移动到如下的六个格子中任意一个 !imghttps://vj.cs
并查集加速区间修改例题
E Packing Under Range Regulationshttps://atcoder.jp/contests/abc214/tasks/abc214e 题目描述： n个球，每个球只能放在l,r的任意一个盒子中，每个盒子只能放一个
二分图之匈牙利算法
二分图定义 二分图又称作二部图，是图论中的一种特殊模型。 设G=V,E是一个无向图，如果顶点V可分割为两个互不相交的子集A,B，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集i in A,j in B，则称图G为
关于SPFA——他死了……
单源最短路奇技淫巧之SPFA算法 !【洛谷日报16】SPFA算法教学https://pic4.zhimg.com/v24c9799ea33fb1fafe422e886674e067c1440w.jpg?source=172ae18b 引入
最小生成树之Kruskal算法
最小生成树之Kruskal算法 定义： 对于无向有环图，如果任意两个顶点都联通并且是一棵树，那么我们就称之为生成树 对于代权值的图，那么权值之和最小的生成树即为最小生成树 Kruskal算法 说白了，Kruskal算法就是大贪心！ 对于m条
最短路算法详解
最短路 图论基础知识——有向图、无向图 有向图： 即单向边，ij有边不一定满足ji有边 无向图： 即双向边，ij有边一定满足ji有边 主要是根据题目要求来建单向边还是双向边 如果是双向边，我们只需要把他拆成ij和ji的两条单向边就行 无论是
二分图的一点点建模例题
全体集合https://ac.nowcoder.com/acm/contest/11220/F 题目描述： 给出 n 个点 m条边 的无向图，给出 k 个点，这 k 个点上每个点都有一个人，每个人每回合能走到一个相邻的节点（不能停留不走），
电路维修「01bfs」
电路维修https://www.acwing.com/problem/content/177/ 题目描述： nm的网格，每个网格上都有一根电线，电线有初始状态，连接左上到右下，或者连接右上到左下，你可以改变若干根电线的状态，使的左上角的格子
冗余路径「边双连通分量、无向图缩点」
冗余路径https://www.acwing.com/problem/content/397/ 题目描述： 为了从 F 个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。 奶牛们已经厌倦了被迫走某一条路，所以她们想建一些
银河「建图 + Tarjan缩点 + 拓扑排序 + 最长路」或者 「差分约束跑最长路 + SPFA的SLF优化」
银河「建图 + Tarjan缩点 + 拓扑排序 + 最长路」https://www.acwing.com/problem/content/370/ 题目描述： 我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 1。现
单词环「二分答案 + SPFA判正环」
单词环https://www.acwing.com/problem/content/1167/ 题目描述： 我们有 n 个字符串，每个字符串都是由 a∼z 的小写英文字母组成的。 如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字
走廊泼水节「并查集 + 贪心」｜｜「最小生成树」
走廊泼水节 题目描述： 给定一颗n个节点的树，你需要增加若干条边，把这颗树扩充为完全图，并满足图的最小生成树是唯一的且是原树，问增加的边的权值总和最小是多少 思路： 完全图指的是图中的任意两点之间都有一条边相连 因为给定的是一棵树，树上的每
AtCoder Beginner Contest 243「E - Edge Deletion」「floyed思维」
E Edge Deletionhttps://atcoder.jp/contests/abc243/tasks/abc243e 题目描述： n个点，m条边，问最多能删掉多少边，使的终图保持和原图一样的连通性，且任意两个点的最短路之间的距离不
观光之旅「floyed求最小环 + 最小环路径」
观光之旅https://www.acwing.com/problem/content/346/ 题目描述： 给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。 你需要输出最小环的方案，若最小环不
牛的旅行「floyed求最短路」
牛的旅行https://www.acwing.com/problem/content/1127/ 题目描述： n个点，给出每个点的二维坐标，再给出nn的01关系图，0代表相连，1代表不相连，会形成若干个连通块，规定一个连通块的直径是块中任意
观光「次短路计数」
观光https://www.acwing.com/problem/content/385/ 题目描述： n个点，m条有向边，起点s，终点f，假设s到f的最短路距离为dis,问s到f的路径中权值为dis和dis1的数量 思路： 同样是最短路计
P1073 最优贸易「记忆化搜索」或者「分层图最短路」或者「双重SPFA」
P1073 \NOIP2009 提高组\ 最优贸易https://www.luogu.com.cn/problem/P1073 题目描述： n个城市，m条边，一部分是单向边，一部分是双向边，每个城市的水晶球的价格不一定相同，你可以在任意一个
昂贵的聘礼「最短路」「思维」
昂贵的聘礼https://www.acwing.com/problem/content/905/ 题目描述： n个物品，每个物品都有一个价值，且每个物品x都有一个替代队列，这个替代队列中，每个替代品y都有一个优惠价格c，你可以使用一个替代品
什么是SPFA？SPFA怎么判负环？怎么判正环？
什么是SPFA SPFA是在BellmanFord的基础上进行的一种优化，BellmanFord的思路是进行n1次循环，每次循环都遍历每一条边来更新最短路，复杂度是 On\m，不难发现每次遍历边uv去更新disv时，当且仅当disu被更新过
图论——连通性
定义 割点：对于一个点x，如果从图中删去x以及与x相连的所有的边，图不再联通，则称x为割点 割边：对于一条边e，从图中删去e，图不联通，则称e为割边 一个图如果不存在割点，则它是一个点双连通图，一个图的极大点双连通子图是他的点双连通分量 一
拓扑排序详解
什么是拓扑排序？ 先穿袜子再穿鞋，先当孙子再当爷。这就是拓扑排序！ 拓扑排序说白了其实不算一种排序，但又像是一种排序（我是不是说了个废话qwq） 他其实是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线
单源最短路之迪杰斯特拉算法Dijkstra
单源最短路之迪杰斯特拉算法（Dijkstra） 问题定义： 求解单源点的最短路径问题：给定带权有向图G和源点s，求点s到图G中其他点的最短路径 可以采用迪杰斯特拉算法（Dijkstra），或者SPFA算法，这里我先介绍一下第一种Dijkst
拓扑排序
拓扑排序 定义： 拓扑排序指的是有向无环图所有顶点的线性序列 该序列需满足俩个条件： 每个顶点只出现一次 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面 有向无环图（DAG图）才有拓扑排序，且可能不止