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. An example is given in Figure 1.
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
Output
5 2
题意：有n个人，告诉你这些人中两两之间的浪漫关系，让你找出最大的集合，使得集合内任何两个学生都没有发生浪漫关系
解题思路：二分图，点独立数=n-点覆盖数，点独立数就是最多的点使得任意两点之间都没有直接联系
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <climits> #include <functional> using namespace std; #define LL long long const int INF=0x3f3f3f3f; int n; int x[1005],y[1005]; int s[1005],nt[30050],e[30050]; int visit[1005]; bool path(int k) { for(int i=s[k];~i;i=nt[i]) { int ee=e[i]; if(!visit[ee]) { visit[ee]=1; if(y[ee]==-1||path(y[ee])) { y[ee]=k; x[k]=ee; return 1; } } } return 0; } void MaxMatch() { int ans=0; memset(x,-1,sizeof x); memset(y,-1,sizeof y); for(int i=0;i<n;i++) { if(x[i]==-1) { memset(visit,0,sizeof visit); if(path(i)) ans++; } } printf("%d\n",n-ans/2); } int main() { while(~scanf("%d",&n)) { int cnt=1,ee,ss,k; memset(s,-1,sizeof s); memset(nt,-1,sizeof nt); for(int i=1;i<=n;i++) { scanf("%d: (%d)",&ss,&k); for(int j=1;j<=k;j++) { scanf("%d",&ee); nt[cnt]=s[ss],s[ss]=cnt,e[cnt++]=ee; } } MaxMatch(); } return 0; }