Posted on 2008-04-23 15:54
superman 阅读(313)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1137 C++ 00:07.49 1820K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, match[1000];
7 bool map[1000][1000], visited[1000];
8
9 bool dfs(int p)
10 {
11 for(int i = 0; i < n; i++)
12 if(map[p][i] && visited[i] == false)
13 {
14 visited[i] = true;
15 if(match[i] == -1 || dfs(match[i]))
16 {
17 match[i] = p;
18 return true;
19 }
20 }
21 return false;
22 }
23
24 int main()
25 {
26 while(cin >> n)
27 {
28 memset(map, false, sizeof(map));
29 memset(match, 255, sizeof(match));
30
31 int s, t, m;
32 for(int i = 0; i < n; i++)
33 {
34 scanf("%d: (%d)", &s, &m);
35 while(m--)
36 {
37 cin >> t;
38 map[s][t] = true;
39 }
40 }
41
42 int cnt = 0;
43 for(int i = 0; i < n; i++)
44 {
45 memset(visited, false, sizeof(visited));
46 cnt += dfs(i);
47 }
48 cout << n - cnt / 2 << endl;
49 }
50
51 return 0;
52 }
53