题目：
Girls and Boys
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 189 Accepted Submission(s): 127
Problem Description
the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set.The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description:the number of studentsthe description of each student, in the following formatstudent_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 …orstudent_identifier:(0)The student_identifier is an integer number between 0 and n-1, for n subjects.For each given data set, the program should write to standard output a line containing the result.
Output
Sample Input
70: (3) 4 5 61: (2) 4 62: (0)3: (0)4: (2) 0 15: (1) 06: (2) 0 130: (2) 1 21: (1) 02: (1) 0
Sample Output
52
Source
Southeastern Europe 2000
Recommend
JGShining
，使得每一条边都分别连接中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。图 1 是一个二分图。为了清晰，我们以后都把它画成图 2 的形式。
匹配：在图论中，，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。例如，图 3、图 4 中红色的边就是图 2 的匹配。
我们定义匹配点、匹配边、未匹配点、非匹配边，它们的含义非常显然。例如图 3 中 1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。图 4 是一个最大匹配，它包含 4 条匹配边。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。图 4 是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。
举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。
代码如下：
/* * b.cpp * * Created on: 2015年3月13日 *Author: Administrator */#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 1001;int map[maxn][maxn];int link[maxn];int useif[maxn];int n;/** * 判断t结点能否找到匹配的节点 */bool can(int t){int i;for(i = 0 ; i < n ; ++i){//遍历所有的结点//如果i结点还没有匹配 && t结点愿意和i结点匹配if(useif[i] == false && map[t][i] == true){useif[i] = true;//那么,将i结点标记为已经匹配//如果i结点目前目前还没有匹配的节点 || i结点匹配的节点能够找到其他匹配的节点if(link[i] == -1 || can(link[i])){link[i] = t;//那么江i结点匹配的结点更新为t结点return true;//返回true,表示t结点可以找到匹配的节点}}}return false;//如果遍历上面的所有节点都未能找到匹配的节点,则返回false.表示未能为t找到匹配结点}/** * 求最大匹配数 */int max_match(){int num = 0;int i;for(i = 0 ; i < n ; ++i){//遍历所有节点,求最大匹配数memset(useif,false,sizeof(useif));if(can(i) == true){num++;}}return num;//泛会所求道的最大匹配数}int main(){while(scanf("%d",&n)!=EOF){memset(map,false,sizeof(map));memset(link,-1,sizeof(link));int i;int a,b;for(i = 0 ; i < n ; ++i){scanf("%d: (%d)",&a,&b);int c;int j;for(j = 0 ; j < b ; ++j){scanf("%d",&c);map[a][c] = true;//表示a愿意和c匹配}}printf("%d\n",n-max_match()/2);//求最大独立集数}return 0;}
有人说,幸福是一种人生的感悟，一种个人的体验。
