Posted on 2008-04-10 18:18
superman 阅读(248)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1134 C++ 00:07.71 9716K */
2 #include <stdio.h>
3 #include <iostream>
4
5 using namespace std;
6 const int N = 1500;
7
8 struct { int cnt, son[1500]; } Tree[1500];
9
10 int f[1500][2];
11 void PostOrder(int p)
12 {
13 if(Tree[p].cnt == 0)
14 {
15 f[p][0] = 0;
16 f[p][1] = 1;
17 return;
18 }
19 for(int i = 0; i < Tree[p].cnt; i++)
20 PostOrder(Tree[p].son[i]);
21
22 f[p][1]++;
23 for(int i = 0; i < Tree[p].cnt; i++)
24 {
25 f[p][0] += f[Tree[p].son[i]][1];
26 f[p][1] += min(f[Tree[p].son[i]][0], f[Tree[p].son[i]][1]);
27 }
28 }
29
30 int main()
31 {
32 int n;
33 while(cin >> n)
34 {
35 memset(Tree, 0, sizeof(Tree));
36 memset(f, 0, sizeof(f));
37
38 int s, m = 0;
39 bool x[1500] = {false};
40 for(int i = 0; i < n; i++)
41 {
42 scanf("%d:(%d)", &s, &m);
43 for(int i = 0; i < m; i++)
44 {
45 Tree[s].cnt = m;
46 cin >> Tree[s].son[i];
47 x[Tree[s].son[i]] = true;
48 }
49 }
50 int root;
51 for(int i = 0; i < n; i++)
52 if(x[i] == false)
53 {
54 root = i;
55 break;
56 }
57
58 PostOrder(root);
59
60 cout << min(f[root][0], f[root][1]) << endl;
61 }
62
63 return 0;
64 }
65