HDU2094 产生冠军

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2094

题意：中文题，就不解释了。题意已经非常清楚了。

这道题的看起来像是一个拓扑排序的问题实际上拓扑感觉做不了，可能可以做了吧？但是我没想到，估计也比较麻烦吧。这里介绍一种比较简单的做法，就是一种思维，如果存在冠军（所有人都可以被他打败），这个人肯定没有败过，而其他人都败过，所以我们只需要确定所有人的人数，和败者的人数（去重以后，所以需要用set，因为一个败者会败给多个人，所以在多个对局中出现）。如果所有人的数量与败者的数量的差是1，说明存在冠军，否则，不存在，直接看代码吧！

//Author: xiaowuga

#include <bits/stdc++.h>

#define maxx INT_MAX

#define minn INT_MIN

#define inf 0x3f3f3f3f

const long long N=;

using namespace std;

typedef long long L;

set<string>a,b;

int main() {

    ios::sync_with_stdio(false);cin.tie();

    int n;

    while(cin>>n&&n){

        a.clear();b.clear();

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

            string x,y;

            cin>>x>>y;

            a.insert(x);

            a.insert(y);

            b.insert(y);

        }

        if(a.size()-b.size()==) cout<<"Yes"<<endl;

        else cout<<"No"<<endl;

    }

    return ;

}

很简单的一道题，主要靠思维吧，感觉和拓扑没什么关系。

巴特西

hdu2094—看似拓扑实际上是一道思维题

HDU2094 产生冠军

最新文章

热门文章