萌新求助
查看原帖
萌新求助
547908
NightTide楼主2022/9/30 18:01
#include<bits/stdc++.h>
#define MAXN 210
using namespace std;
struct edge{ int pre, to; };
edge e[MAXN << 1];
map<string, int> book;
int n, cnt, tot;
int head[MAXN], dp[MAXN][2], f[MAXN][2];
string name;
void add_edge(int u, int v){
    e[++cnt].pre = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}
void dfs(int now){
    dp[now][1] = 1;
    for(int i = head[now]; i; i = e[i].pre){
        dfs(e[i].to);
        dp[now][1] += dp[e[i].to][0];
        f[now][1] |= f[e[i].to][0];
        dp[now][0] += max(dp[e[i].to][1], dp[e[i].to][0]);
        if(dp[e[i].to][1] == dp[e[i].to][0]) f[now][0] = 1;
        else if(dp[e[i].to][1] > dp[e[i].to][0]) f[now][0] |= f[e[i].to][1];
        else f[now][0] |= f[e[i].to][1];
     }
}
int main(){
    while(~scanf("%d",&n)){
        if(n == 0) break;

        book.clear(); cnt = 0; tot = 0;
        memset(f, 0, sizeof(f));
        memset(dp, 0, sizeof(dp));
        memset(head, 0, sizeof(head));

        cin >> name; book[name] = ++tot;
        for(int i = 1; i < n; i++){
            int u, v;
            cin >> name;
            if(!book.count(name)) book[name] = ++tot;
            u = book[name];
            cin >> name;
            if(!book.count(name)) book[name] = ++tot;
            v = book[name];
            add_edge(v, u);
        }
        dfs(1);
        printf("%d ",max(dp[1][0],dp[1][1]));
        if(dp[1][1] == dp[1][0]) printf("No\n");
        else if(dp[1][1] > dp[1][0]){
            if(f[1][1]) printf("No\n");
            else printf("Yes\n");
        }else{
            if(f[1][0]) printf("No\n");
            else printf("Yes\n");
        }
    }
    return 0;
}

WA,求助大佬

2022/9/30 18:01
加载中...