hdu 1068 Girls and Boys (二分图的最大独立集，匈牙利算法)
hdu 1068题目链接 题意：有n个同学。。给出同学之间的 爱慕关系。。。选出一个集合使得集合中的人没有爱慕关系。问能选出的最大集合是多少。
思路：没有数据范围，差评！题意说得也不清楚。。由数据知道。。爱慕关系一定是相互的。。。
这道题实际上是二分图的最大独立集问题。
**最大独立集问题： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值**
学到的一点是：对于二分图，可能并不能明显得分成两个不相交的集合，而是一个整体。（有左集合到又集合的边，同时有又集合到左集合的边，就是说每条边都是无相边。。？） 这其实等于把两个无向图叠加在了一起（从左指向右的和从又指向左的）
所以hungary得到的最大匹配数应该除以2，才是真正的最大匹配数。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月28日 星期六 08时42分19秒
4File Name :code/hdu/1068.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E3+5;
34int n;
35int head[N];
36//vector <int>edge[N];
37int link[N];
38bool vis[N];
39
40int cnt;
41struct Edge
42{
43 int v;
44 int nxt;
45}edge[10005];
46
47void addedge( int u,int v)
48{
49 edge[cnt].v = v;
50 edge[cnt].nxt = head[u];
51 head[u] = cnt;
52 cnt++;
53}
54
55int dfs ( int u)
56{
57 for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
58 {
59 int v = edge[i].v;
60 if (vis[v]) continue;
61 vis[v] = true;
62
63 if (link[v]==-1||dfs(link[v]))
64 {
65 link[v] = u ;
66 return true;
67 }
68 }
69 return false;
70}
71int hungary()
72{
73 ms(link,-1);
74
75 int res = 0 ;
76 for ( int i = 1 ; i <= n ; i++)
77 {
78 ms(vis,false);
79 if (dfs(i)) res++;
80 }
81 return res/2;
82}
83
84int main()
85{
86 #ifndef ONLINE_JUDGE
87 freopen("code/in.txt","r",stdin);
88 #endif
89
90 while (scanf("%d",&n)!=EOF)
91 {
92
93 cnt = 0 ;
94 ms(head,-1);
95
96 for ( int i = 1 ; i <= n ; i++)
97 {
98 int id,num;
99 scanf("%d: (%d)",&id,&num);
100 id++;
101 while (num--)
102 {
103 int x;
104 scanf("%d",&x);
105 x++;
106 addedge(id,x);
107 }
108 }
109
110 int ans = n-hungary();
111
112 printf("%d\n",ans);
113 }
114
115
116 #ifndef ONLINE_JUDGE
117 fclose(stdin);
118 #endif
119 return 0;
120}