Girls and Boys
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7711 Accepted Submission(s): 3536
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.
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
5 2
/* 题解：
题目要求男女最大的无关系集合，即是求二分图的最大独立集，可以先求出最大匹配数。
根据公式最大独立集 = 节点数 - 最大匹配数，可求出最大独立集。
*/
//注意：此题特殊之处在于未指出男女生编号，匹配数/2为真正最大匹配数。
//这种未指明男女编号的最大独立集：n-匹配数/2
//求最大匹配数，这里用的是匈牙利算法。
#include<cstdio>
#include<cstring>
int n,m;
int map[1010][1010],vis[1010],girl[1010];
bool find(int x)
{
int j;
for(j=0; j<n; j++)
{
if(map[x][j]==true&&vis[j]==false)
{
vis[j]=1;
if(girl[j]==0||find(girl[j]))
{
girl[j]=x;
return true;
}
}
}
return false;
}
int main()
{
int t,i,j,k,a,b,ans;
while(scanf("%d",&t)!=EOF)
{
n=m=t;
memset(girl,0,sizeof(girl));
memset(map,0,sizeof(map));
while(t--)
{
scanf("%d: (%d)",&a,&k);
for(i=0; i<k; i++)
{
scanf("%d",&b);
map[a][b]=1;
}
}
for(i=0,ans=0; i<m; i++)
{
memset(vis,0,sizeof(vis));
if(find(i)) ans++;
}
printf("%d\n",n-ans/2);
}
return 0;
}