二分图文章列表
[POJ2594] Treasure Exploration（最小路径覆盖-传递闭包 + 匈牙利算法）
传送门 引子： 有一个问题，是对于一个图上的所有点，用不相交的路径把他们覆盖，使得每个点有且仅属于一条路径，且这个路径数量尽量...二分图,匈牙利算法,最小路径覆盖,Floyd
[POJ2446] Chessboard（二分图最大匹配-匈牙利算法）
传送门 把所有非障碍的相邻格子彼此连一条边，然后求二分图最大匹配，看 tot * 2 + k 是否等于 n * m 即可。 但是连边不能重复，比如 a 格子 和 b 格子 相邻，不能 a 连 b ，b...二分图,匈牙利算法,最大匹配
运动员最佳匹配问题（km算法）
洛谷传送门 带权二分图最大权完美匹配。 裸的km算法。 注意开long long。 1 #include cstdio 2 #include cstring 3 #include iostream 4...二分图,KM算法,最大权完美匹配
【模板】二分图最大权完美匹配KM算法
hdu2255模板题 KM是什么意思，详见 百度百科 。 总之知道它可以求二分图最大权完美匹配就可以了， 时间复杂度为O(n^3) 。 给张图。 二分图有了边权，求最大匹配下的最大权值。 所以该怎么做...模板,二分图,KM算法,最大权完美匹配
飞行员配对方案问题（匈牙利算法+sort）
洛谷传送门 匈牙利算法+sort 没什么好说的。 ——代码 1 #include cstdio 2 #include cstring 3 #include algorithm 4 5 using na...二分图,匈牙利算法,stl,最大匹配,网络流
【转】二分图的一大坨定理
转自：cnblogs/zarth/p/6417088 一、二分图最大匹配 定义：匹配是图中一些边的集合，且集合中任意两条边都没有公共点，所有的匹配中，边数最多的就是最大匹配。 算法：用匈牙利算法可以在...二分图,模板
[USACO11NOV]牛的障碍Cow Steeplechase（匈牙利算法）
洛谷传送门 题目描述： 给出N平行于坐标轴的线段，要你选出尽量多的线段使得这些线段两两没有交点（顶点也算），横的与横的，竖的与竖的线段之间保证没有交点，输出最多能选出多少条线段。 因为横的与横的，竖的...二分图,匈牙利算法,最大匹配
【模板】判断二分图
给你一个 无向图 ， 让你判断这是不是一个二分图。 二分图的标准：可以把这个图的点分成两堆，试每条边都连接这两个堆里的点，而一个堆里的点不能相连。 无向图G为二分图的充分必要条件是，G至少有两个顶点,...模板,二分图
Divide Groups（分组）（二分图染色）
题目链接 题目大意是说输入数字n 然后告诉你第i个人都认识谁？ 让你把这些人分成两堆，使这每个堆里的人都互相认识。 做法：把不是互相认识的人建立一条边，则构建二分图，两堆的人肯定都互相认识，也就是说，...二分图
【模板】二分图匹配
洛谷模板题 学了匈牙利算法。 匈牙利算法核心是找增广路经。 可以求出二分图的最大匹配数。 感觉还是挺好理解的。 时间复杂度 邻接矩阵： 邻接表： 空间复杂度 邻接矩阵： 邻接表： 看的这个 blog ...二分图,模板,最大流,匈牙利算法,最大匹配
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化