为什么不问问神奇海螺呢
为什么不问问神奇海螺呢
全部文章
图论之二分图
2018暑假组队赛记录(1)
ACM_心情(6)
codeforces2018(7)
DFS/BFS搜索(10)
Linux-Ubuntu(1)
python(1)
STL(12)
二分搜索(9)
健身(2)
几何之凸包问题(10)
几何之半平面交(6)
几何之旋转卡壳(2)
几何之模拟退火(5)
几何之面积问题(9)
几何技巧(7)
几何问题非模板问题(5)
动态规划之基础DP(54)
动态规划之状态压缩(1)
图论之强联通SCC(5)
图论之网络流(8)
套题(2)
学习(10)
学习资料(28)
年月问题(3)
思维(47)
括号匹配(2)
数学之博弈(6)
数据结构之Manacher(2)
数据结构之单调队列(1)
数据结构之字典树(3)
数据结构之字符串匹配KMP(4)
数据结构之并查集(10)
数据结构之生成树(3)
数据结构之线段树/树状数组(11)
数据结构之莫队算法(1)
数论之Mobius莫比乌斯反演(6)
数论之Nim博弈及变形(2)
数论之伯努利数(1)
数论之佩尔方程(4)
数论之因数相关(1)
数论之数学期望(2)
数论之组合数学(8)
数论之质数相关(1)
数论之进制转换(1)
暴力题(14)
未归档(37)
构造题(3)
模拟(9)
模板集合(打印)(9)
玄学黑科技(1)
生活分享(2)
电影(2)
算法学习(18)
自然溢出(1)
规律(7)
读书(7)
读书笔记(7)
贪心(21)
随机or玄学(1)
高精度(1)
归档
标签
去牛客网
登录
/
注册
Conchpeng
贵在坚持
全部文章
/ 图论之二分图
(共5篇)
关于二分图
1.二分图的判定: BFS,不能有奇数的环(引理) 2.二分图最大匹配(匈牙利算法,增广路) 3.二分图建模... 主要能看到把一个集合分成2个内部无边的集合.边可以是某种关系. 并且最大匹配数/最小覆盖点数.正好是题目要求的答案 4.多重匹配和带权最大匹配用 网络流解决 5.二分图最小点覆...
2018-07-19
0
503
Machine Schedule HDU - 1150
Machine Schedule 题意:A,B两个机器,每个机器有M种模式a[M],b[M].现在有N个任务,每个任务需要a[i]或者b[i].每当机器转换一种机器模式,问至少转换多少次机器模式? 思路:对于a[i],b[i]连一条边.即求至少多少个点,能把整个二分图的边至少有一个端点覆盖.即二...
2018-07-19
0
664
車的放置[二分图最大匹配数]
車的放置 题意:n*m的棋盘上有t个位置被禁止放置东西,问最多可以放置多少个"车" 思路:我们必须找到2个集合,每个集合内部没有边,每一条边的两个端点在两个集合.以行坐标为A集合,列坐标为B集合 那么A,B内部均无边,且所有边的两个端点都在两个集合里 一个端点只能属于一条...
2018-07-19
0
474
4949: 棋盘覆盖[二分图最大匹配]
4949: 棋盘覆盖 题意:一个n*n的棋盘,现在有m个位置是禁止放东西的,问最多可以放多少个 1 * 2 的骨牌 , 输出结果 思路:n*n地图上能放骨牌的所有方格中心点连边,我们可以发现,这些边可以构成一个二分图,在对角线关系的所有点都是一个集合,并且集合内部没有边.现在求二分图的最大匹配...
2018-07-18
0
685
4844: Noip2010 关押罪犯[BFS判二分图]
4844: Noip2010 关押罪犯 题意:有n名罪犯,有m对关系a,b,c分别代表罪犯a和罪犯b有矛盾值c. 现在将这些囚犯放到2个监狱(集合),问最少的矛盾值会是多少 思路:二分最少的矛盾值mid,如果边权<=mid不影响结果,对于>mid的所有边,看是否能形成一张二分图 ...
2018-07-18
0
482