解题报告 http://blog.csdn.net/juncoder/article/details/38159017 题目传送门 题意： 看到题目我就笑了，，， 老师认为这样的两个学生不是一对： 身高相差40以上（年龄都不是距离了，身高又算什么） 不同性别（sad，，，就不允许基友存在呀，，，谁的肥皂掉了，，，） 喜欢不一样的歌曲类型（你总不能要求两人整天听小苹果吧,,,,,,

UVA 12083 - Guardian of Decency 题目链接 题意：给定一些男女，满足身高差不大于40，喜欢同一种音乐，不喜欢同一种体育项目，并且性别不同，就可能发生关系，现在老师要带一些男女出去玩，要求不能有一对发生关系，问最多能带多少人 思路：分男女，把会发生关系的连边，然后做最大匹配，最后n-最大匹配就是最多能带的人 代码： #include <cstd

Problem Solution 原题要求选出的点中任意两点需至少满足一个条件，可以在四个条件都不满足的点间连边，所得图为二分图（一边男一边女），等价于求二分图的最大独立集。 二分图最大独立集与最小覆盖集 二分图最独立集大小=结点数-最大匹配（这里的最大匹配可以看成选择有边相连的两个点时要去掉其中一个，最大匹配数即为最小要去掉的点数，同时也是最小覆盖）。覆盖集：对于每条边，至少有一个点

题目链接：https://vjudge.net/problem/UVALive-3415         题解： 题意：选出尽可能多的人， 使得他（她）们之间不会擦出火花。即求出最大独立集。 1.因为性别有男女之分，所以此题的模型是个天然的二分图。 2.如果两个人之间可能擦出火花（即4条限定都不满足），则在他和她之间连一条边。 3.用匈牙利算法求出最小覆盖点数（即最大匹配数），然后最大独立

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34831   【思路】        二分图的最大独立集。              即在二分图中选取最多的点，使点与点之间不相邻。        最大独立集为最小覆盖集的补集。        男者X结点，女者Y结点，连边(Xi,Yj)当且仅当两者

题目链接：http://poj.org/problem?id=2771 题目意思：有一个保守的老师要带他的学生来一次短途旅行，但是他又害怕有些人会变成情侣关系，于是就想出了一个方法： 1、身高差距  > 40cm 2、相同性别 3、喜欢的音乐种类  不同 4、有共同喜爱的 运动       只要满足其中这4个条件中的一个（当然越多越好啦），就可以将他们编为一组啦（一组两个人），求能被编为一组的最

题意：人与人之间满足4个条件之一即不能成为一对（也就说这4个条件都不满足才能成为一对），求可能的最多的单身人数。 思路：把男女分为两部分，接下来就是二分图的匹配问题。把能成为一对的之间连边，然后求出最大匹配。题目要求的是最大独立数。 最大独立数=顶点数-最大匹配数 #include<iostream>#include<stdio.h>#include<string.h>#inclu

题意：有N个学生，现要从中选出尽量多的学生，使得选出来的学生中任意两个学生满足至少满足下列4个条件中的1个： 1.身高相差超过40 2.同性 3.喜欢的音乐类型不同 4.喜欢的运动类型相同 问最多能选出多少个学生（测试组数T <= 100, N <= 500, 音乐类型和运动类型的字符串长度不超过100）。 题目链接：https://icpcarchive.ecs.baylor.edu