题解 P1701 [USACO19OPEN] Cow Evolution B

题目分析

我们需要判断给定的子种群特性集合是否能构成一棵合法的进化树，即每个特性只能在进化树的一条边上出现一次。后悔模拟赛时没有做出来。

核心思路

特性进化关系的三种情况

在合法的进化树中，任意两个特性 A 和 B 的关系只能是以下三种情况之一：

1. A 在 B 之前进化：所有有 B 的种群都有 A。
2. B 在 A 之前进化：所有有 A 的种群都有 B。
3. A 和 B 在不同的分支进化：没有种群同时拥有 A 和 B。

非法情况的判断

如果同时存在：

• 有些种群只有 A。
• 有些种群只有 B。
• 有些种群同时有 A 和 B。

这就意味着特性 A 和 B 在进化过程中"交叉"了，违反了"每个特性只能出现一次"的规则。

算法实现

对于任意两个特性 trait1 和 trait2，定义三个标志：

• f1：是否存在同时包含两个特性的子种群。
• f2：是否存在只包含 trait1 不包含 trait2 的子种群。
• f3：是否存在只包含 trait2 不包含 trait1 的子种群。

非法条件：f1 && f2 && f3。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=30;

int main(){
    int n,k;
    vector<string> a[N];  // 存储每个子种群的特性列表
    
    // 输入数据
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k;
        string s;
        for(int j=1;j<=k;j++){
            cin>>s;
            a[i].push_back(s);
        }
    }
    
    // 收集所有不同的特性
    set<string> st;
    for(int i=1;i<=n;i++){
        for(auto x:a[i]){
            st.insert(x);
        }
    }
    
    // 检查每对特性的关系
    for(auto x:st){
        for(auto y:st){
            if(x==y) continue;
            
            int f1=0, f2=0, f3=0;
            for(int i=1;i<=n;i++){
                int fx=0, fy=0;
                for(auto z:a[i]){
                    if(z==x) fx=1;
                    if(z==y) fy=1;
                }
                if(fx&&fy) f1=1;
                else if(fx&&!fy) f2=1;
                else if(!fx&&fy) f3=1;
            }
            
            // 如果三个条件同时满足，说明特性交叉
            if(f1&&f2&&f3){
                cout<<"no";
                return 0;
            }
        }
    }
    
    cout<<"yes";
    return 0;
}

复杂度分析

• 特性总数 $M \leq 25 \times 25 = 625$（实际远小于此）。
• 子种群数 $N \leq 25$。
• 时间复杂度：$O(M^2 \times N)$，在数据范围内完全可行。

举例说明

合法例子

种群1: spots, firebreathing
种群2: (无特性)
种群3: flying  
种群4: telepathic, flying

非法例子

种群1: A
种群2: B
种群3: A, B

检查特性对 (A, B) 时发现三个条件同时满足，因此输出 "no"。

完结撒花！！！