题意：

•Mocrosoft software这个公司有N个员工。除了老板（BillHates）以外，其他每个人都有一个自己的上司。现在过年了，老板打算给员工们发奖金。为了让支出最少，现在有三个规则：

·Eachprogrammer may either assign a grant to one of his subordinates or have a grantassigned to him by his chief or none of the above.

一、每个员工可以安排自己的下属拿奖金，可以等待拿自己上司给自己的奖金。也可以什么都不做。（就是说

他给下属安排奖金后，他就不能有奖金了）

·Noprogrammer can simultaneously receive a grant and assign a grant to one of hissubordinates.

二、没有哪一个程序猿可以同时接收上司给的奖金，还给自己下属安排奖金。

（就是说他给下属安排奖金后，他就不能由奖金了！）

·Noprogrammer can assign a grant to more than one of his subordinates

三、每个程序猿最多只能给自己的一个下属（要是他有下属的话）安排奖金。

注意：每次输入的数是下一个点的父亲的编号，所以题中的输入就是一颗从上往下的树了，编写程序时从下往上找即可。

 1 #include<stdio.h>  
 2 #include<string.h>  
 3   
 4 const int maxn = 500000+10;  
 5   
 6 int p[maxn]; // 记录父亲  
 7 int vis[maxn]; // 标记是否分到钱  
 8 int ans[maxn]; // 记录分到钱的员工编号  
 9   
10 int main()  
11 {  
12     int n;  
13     while(scanf("%d", &n) != EOF)  
14     {  
15         int sum = 0;  
16         for(int i = 2; i <= n; i++)  
17         {  
18             scanf("%d", &p[i]);  
19         }  
20   
21         memset(vis, 0, sizeof(vis)); // 初始化  
22         for(int i = n; i > 1; i--) // 从最底层的节点开始找  
23         {  
24             if(!vis[i] && !vis[p[i]]) //如果自己没有分到钱，而且父亲和兄弟也没有分到钱  
25             {  
26                 vis[i] = 1;  
27                 vis[p[i]] = 1;  
28                 ans[sum++] = i; // 分钱  
29             }  
30         }  
31         printf("%d
", sum*1000);  
32         for(int i = sum-1; i >= 0; i--)  
33         {  
34             if(i == (sum-1)) printf("%d", ans[i]);  
35             else printf(" %d", ans[i]);  
36         }  
37         printf("
");  
38     }  
39     return 0;  
40 }

这类树的模型见得少，看到就头晕。

Sarov zoneshttp://acm.sgu.ru/problem.php?contest=0&problem=171

http://blog.csdn.net/cfreezhan/article/details/8007554

奇葩的题目，这个题目大意更让人咋舌！！直接上代码。

 1 #include<cstdio>  
 2 #include<cstring>  
 3 #include<algorithm>  
 4 using namespace std;  
 5 const int MAXK=100+10;  
 6 const int MAXN=16000+10;  
 7 struct Zone  
 8 {  
 9     int index;//编号  
10     int N;//需要的人数  
11     int Q;//进入该区域的分数线  
12 }zone[MAXK];  
13 struct Stu  
14 {  
15     int index;//编号  
16     int P;//水平  
17     int w;//重量  
18 }stu[MAXN];  
19 int p[MAXN];  
20 bool cmp1(Zone a,Zone b)//按照Q从大到小排序  
21 {  
22     return a.Q>b.Q;  
23 }  
24 bool cmp2(Stu a,Stu b)//按照w从大到小排序  
25 {  
26     return a.w>b.w;  
27 }  
28 int main()  
29 {  
30     int k;  
31     int i,j;  
32     int num=0;  
33     scanf("%d",&k);  
34        
35     for(i=0;i<k;i++)  
36     {  
37         zone[i].index=i+1;  
38         scanf("%d",&zone[i].N);  
39         num+=zone[i].N;  
40     }  
41     for(i=0;i<k;i++)  
42         scanf("%d",&zone[i].Q);  
43     sort(zone,zone+k,cmp1);  
44     for(i=0;i<num;i++)  
45     {  
46         stu[i].index=i+1;  
47         scanf("%d",&stu[i].P);  
48     }  
49     for(i=0;i<num;i++)  
50         scanf("%d",&stu[i].w);  
51     sort(stu,stu+num,cmp2);  
52     memset(p,-1,sizeof(p));  
53     for(i=0;i<num;i++)//第一轮先分配成绩达到了的  
54     {  
55         for(j=0;j<k;j++)  
56         {  
57             if(stu[i].P>zone[j].Q && zone[j].N)//注意：是stu[i].P>zone[j].Q不是>=  
58             {  
59                 p[stu[i].index]=zone[j].index;  
60                 zone[j].N--;  
61                 break;//依次对排好序的学生逐个从排好序的区域逐个安排  
62             }//也就是说对下一个学生也从第一个区域开始排  
63         }  
64     }  
65     j=0;  
66     for(i=0;i<num;i++)//分配剩下的人  
67     {  
68         if(p[i+1]!=-1)  
69            continue;//表示已经分配  
70         while(zone[j].N==0)  
71            j++;//表示当前区域已经招满  
72         p[i+1]=zone[j].index;  
73         zone[j].N--;  
74     }  
75     for(i=1;i<=num;i++)  
76     printf("%d ",p[i]);  
77     return 0;  
78 }

不懂就进前面渊神的说明：