《【调研研究分析报告】1137 Girls and Boys解题报告(mine)》由会员分享，可在线阅读，更多相关《【调研研究分析报告】1137 Girls and Boys解题报告(mine)（8页珍藏版）》请在金锄头文库上搜索。
1、1137GirlsandBoys最大点独立集 二部图的最大匹配 题目描述 大二的时候 某人开始了一项研究 研究同学之间的浪漫关系 romanticallyinvolved 关系被定义为一个男孩和一个女孩之间的关系 为了研究的需要 有必要找出满足条件的最大集合 集合内任何两个学生都没有发生 romanticallyinvolved 关系 程序需要输出该集合中学生的人数 输入 输出描述 输入描述 输入文件中包含若干组数据 每组数据代表一组研究对象 描述如下 学生人数对每个学生的描述 遵循如下格式 学号 关系的数目 学号1学号2学号3 或者是学号 0 对 500 个人 学号从0到n 1 输出描述 对
2、每组数据输出对应结果 样例输入 输出 70 3 4561 2 462 0 3 0 4 2 015 1 06 2 0130 2 121 1 02 1 0 52 最大顶点独立集为 2 3 4 5 6 如果将每个人用一个点代表 有关系的人之间连一条线 则构成一个二分图 男生之间不会有关系 女生之间也不会有关系 独立集 顶点集合中任意两个顶点不相连 求最大独立集 即点数最多的独立集 求二部图的最大独立集 二部图的最大匹配 若有k条没有公共顶点的边 匹配 则结果一定不大于n k 若最大匹配数是m 则结果不大于n m 随便画了几组 都可以构造出n m个点的点集 由此猜想答案是n m 证明 欲构造出含n m
3、个点的独立集首先选取不与任一条匹配边相关联的所有点 未盖点 记为V 显然这些点之间无边相连 任选一条匹配边 设其顶点为A B若A加入V 后 V 不是独立集 则选取B 若A B均不能选 则可增加一条匹配边 再选一条匹配边 顶点为C D 同上分析 若C D不能加入V 则一定是由于A或者B 而非不在匹配中的点 goon 且此时C D中只有一个可选 不妨设为C 则A B中也是只有一个可选 为B 否则A C可同时加入V 且B C间存在边 说明有未盖点B C 存在边AB DC 及边BC 最大匹配可加一 矛盾 由此 C D中也可选一点加入V 使V 仍是独立集继续选边 加点 直到加入m个点 结论 问题转化成求二分图的最大匹配匈牙利算法
