首页 > 代码库 > 二分图小结
二分图小结
此文意在整理二分图的各种变形。
HDU 1068 Girls and Boys
最基础的二分图匹配问题，简单的求最大匹配数。
HDU 1150 Machine Schedule
无向图 最小点集覆盖 = 最大匹配。
把作业看成边，把机器看成点。
无向图的最小点集覆盖是指存点集K，使得图中的所有边都与K中的某些点相连 ，且去除K任意一点就不再满足前述条件。
HDU1151 Air Raid
DAG的最小路径覆盖 =DAG 顶点数 - 对应二分图的最大匹配。
将DAG中的点一分为二，对于N个点中的第 i 个点 分成 i 与 n+i。
然后对着2*n个点建立无向图。
DAG的最小路径覆盖是指找最小数目的互相不相交的有向路径,满足DAG的所有顶点都被覆盖。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。