POJ_3342_Party_at

#include <iostream>

#include <map>

#include <cstring>

using namespace std;

int Graph[210][210];

int DP[210][2];

int count;

void DFS( int index ){

    DP[index][0] = 0;

    DP[index][1] = 1;

    for( int i = 1; i <= count; ++i ){

        if( Graph[index][i] ){

            DFS(i);

            DP[index][0] += max( DP[i][0], DP[i][1] );

            DP[index][1] += DP[i][0];

        }

    }

}

bool check(){

    for( int i = 1; i <= count; ++i ){

        if( DP[i][0] == DP[i][1] ){

            for( int j = 1; j <= count; ++j ){

                if( Graph[i][j] == 1 && DP[j][0] == DP[j][1] ) return false;

            }

        }

    }

    return true;

}

int main(){

    while( true ){

        memset( Graph, 0, sizeof(Graph) );

        count = 1;

        map<string, int>mapTemp;

        int n;

        cin>>n;

        if( n == 0 ) break;

        string boss;

        cin>>boss;

        mapTemp[boss] = count++;

        for( int i = 2; i <= n; ++i ){

            string son;

            string parent;

            cin>>son>>parent;

            if( !mapTemp[son] ) mapTemp[son] = count++;

            if( !mapTemp[parent] ) mapTemp[parent] = count++;

            Graph[mapTemp[parent]][mapTemp[son]] = 1;

        }

        DFS(1);

        cout<<max(DP[1][0], DP[1][1])<<" ";

        if( n == 1 ){

            cout<<"Yes"<<endl;

            continue;

        }

        if( n == 2 ){

            cout<<"No"<<endl;

            continue;

        }

        if( check() ){

            cout<<"Yes"<<endl;

            continue;

        }

        if(!check()){

            cout<<"No"<<endl;

            continue;

        }

    }

    return 0;

}
巴特西

POJ_3342_Party_at_Hali-Bula

最新文章

热门文章
