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 students
the description of each student, in the following format
student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ...
or
student_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

7
0: (3) 4 5 6
1: (2) 4 6
2: (0)
3: (0)
4: (2) 0 1
5: (1) 0
6: (2) 0 1
3
0: (2) 1 2
1: (1) 0
2: (1) 0

Sample Output

5
2

Source

Southeastern Europe 2000

Recommend

JGShining

题目分析：

二分图，求最大独立集。简单题。当中，最大独立集=节点数-最大匹配数/2。所谓的最大独立集,事实上就是

没有匹配到的点(未匹配点)的集合。

下面介绍一下二分图的一些基本概念：(本来想自己写的，可是发现别人整理的比自己即将要写的要具体。

所以在这里转了一下http://blog.csdn.net/pi9nc/article/details/11848327 的内容)

二分图：简单来说。假设图中点能够被分为两组，而且使得全部边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集 U 和 V 。使得每一条边都分别连接U 、 V 中的顶点。假设存在这种划分。则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。图 1 是一个二分图。为了清晰，我们以后都把它画成图 2 的形式。

匹配：在图论中，一个「匹配」（matching）是一个边的集合，当中随意两条边都没有公共顶点。比如。图 3、图 4 中红色的边就是图 2 的匹配。

Bipartite Graph(1) Bipartite Graph(2) Matching Maximum Matching

我们定义匹配点、匹配边、未匹配点、非匹配边，它们的含义很显然。比如图 3 中 1、4、5、7 为匹配点，其它顶点为未匹配点；1-5、4-7为匹配边。其它边为非匹配边。

最大匹配：一个图全部匹配中，所含匹配边数最多的匹配。称为这个图的最大匹配。图 4 是一个最大匹配，它包括 4 条匹配边。

完美匹配：假设一个图的某个匹配中，全部的顶点都是匹配点，那么它就是一个完美匹配。图 4 是一个完美匹配。

显然，完美匹配一定是最大匹配（完美匹配的不论什么一个点都已经匹配，加入一条新的匹配边一定会与已有的匹配边冲突）。但并不是每一个图都存在完美匹配。

举例来说：例如以下图所看到的，假设在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。是否可能让全部男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中。这就是完美匹配问题。假设换一个说法：最多有多少互相喜欢的男孩/女孩能够配对儿？这就是最大匹配问题。

题目分析：

求最大独立集。最大独立集=节点总数-最大匹配数/2

代码例如以下：

/*
 * 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];//map[i][j]=1,表示第i个女生愿意和第j个男生匹配
int link[maxn];//link[i] = t.表示第i个男生匹配的是女生t
int useif[maxn];//表示第i个男生是否已经匹配

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-max_match()/2);//求最大独立集数
	}

	return 0;
}