进化树 题解

进化树 题解

测试点时限 1s

测试点内存 128M

 分析题目:

第一眼看上我们会想到建树,能否成功建树???

我们从边入手:一个边至多有一个超能力,且一种新特性只能从一个边得,所以每一条有超能力得边都是独一无二!(结论一)

        从中得出凡是有共同超能力的结点都必须经过共同的父节点,即有公共祖先(结论二)!

接下来思考:怎么判断某棵树是否合法?

      节点入手,即一个点能否合法得来:如果没有结论一的话,肯定每种情况都可以建树;但有结论一,我们可以这个节点的父节点入手,得某个结点的进化循序唯一的,在其他(N-1)个节点中找到是它父节点(注意:就算没有也可从祖先一步步进化!!!)如图:发现有两种进化顺序!!!所以这棵树不合法

进化树 题解

·    既然有了判断方法,我们应确定判断循序:我们肯定从最接近祖先开始判断,不断向下(为确保关系),一旦发现某个点不成立,整棵树都不成立。

    

 1 #include<iostream>
 2 #include<fstream>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 int n;
 7 int from;
 8 struct cow{
 9     int n;
10     string str[30];
11 }a[30];
12 bool cmp(cow a,cow b)
13 {
14     return a.n<b.n;
15 }
16 bool check(int x,int y)
17 {
18     if (a[x].n>a[y].n)swap(x,y);
19     bool u;
20     for (int i=1;i<=a[x].n;i++)
21     {
22         u=0;
23         for (int j=1;j<=a[y].n;j++)
24         {
25             if (a[x].str[i]==a[y].str[j])
26             {
27                 u=1;break;
28             }
29         }
30         if (!u)return 0;
31     }
32     return 1;
33 }
34 int main()
35 {
3638     cin>>n;
39     for (int i=1;i<=n;i++)
40     {
41         cin>>a[i].n;
42         for (int j=1;j<=a[i].n;j++)cin>>a[i].str[j];
43     }
44     sort(a+1,a+1+n,cmp);让深度小的排在前面!!!
45     bool ok;
46     for (int i=1;i<=n;i++)
47     {
48         ok=1;
49         from=-1;
50         for (int j=i-1;j>=1;j--)//找父节点,其深度一定小于当前的深度
51         {
52             if (a[i].n>a[j].n&&check(j,i))
53             {
54                 if (from==-1)
55                 {
56                     from=j;
57                 }
58                 else
59                 {
60                     if (check(j,from))from=j;
61                     else
62                     {
63                         ok=0;
64                         break;
65                     }
66                 }
67             }
68         }
69         if(!ok)
70         {
71             cout<<"no";return 0;
72         }
73     }
74     cout<<"yes"<<endl;
75     return 0;
76 }

 

上一篇:B - Dining POJ - 3281 网络流


下一篇:畜栏预定【贪心】