首页
编程日记
ChatGpt专题
LINUX学习
Java学习
前端教程
单片机
服务器
单元测试
C语言数组
unix
开尔文四线法与电桥
编辑器
关联数组
硬件架构
hdfs
dockerfile
产品
skill 命令
gnu
cisp考试难度
深浅拷贝
粘包拆包
android 9
rbac
fiddler
轮廓
染色法
2024/4/16 22:04:34
【算法竞赛模板】二分图(染色法、匈牙利法)
二分图一、定义二、应用三、算法模板① 染色法模板② 匈牙利模板 - 邻接表③ 匈牙利模板 - 邻接矩阵废话不多说,本苟蒻发文,有任何问题欢迎大佬斧正~(>人<;) 一、定义 图的节点由两个集合 u、v…
阅读更多...
图论 - 二分图(染色法、匈牙利算法)
文章目录 前言Part 1:染色法判定二分图1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法 Part 2:匈牙利算法求二分图的最大匹配1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法 前言 本篇博客将介绍两种二分图有关的算法…
阅读更多...
染色法判定二分图算法总结
知识概览 一个图是二分图当且仅当图中不含奇数环(奇数环是边数为奇数的环)。图中不含奇数环,染色过程中一定没有矛盾。染色法判定二分图算法时间复杂度O(n m)。 例题展示 题目链接 860. 染色法判定二分图 - AcWing题库https://www.acwing.…
阅读更多...
acwing 860 染色法判定二分图
题面 题解 二分图定义:图中点可分为两个集合,每个集合中的点互不相邻 二分图性质:当且仅当图中不含奇数环(充要条件) 2. 对于染色过程,我们用树/图的深度遍历,如果当前节点没有染色,就将其染成1,…
阅读更多...
算法竞赛进阶指南 关押罪犯
题面 题解 我们将罪犯当作点,罪犯之间的仇恨关系当作点与点之间的无向边,边的权重就是罪犯之间的仇恨值,那么原来的问题就转化成了把所有点分成两组,使得各组内的边的权重的最大值最小 我们在[0,1e9] 之间二分枚举最大权值x&#…
阅读更多...