2010-1063

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目的意思是，有n个人要进行比赛，现在已经比了m场胜负关系已知的比赛，其中胜负关系是具有传递性的，就是说，如果A胜B，B胜C，那么如果有A和C的比赛，一定是A胜C，否则这个记录就是错的。

接下来还有P场没有记录的比赛，其中比赛的结果要用已经知道的m场的胜负关系推断出来，如果任何一场不能判断，就输出"Can't judge."

这题的做法就是把胜负关系看成有向图的边，读进来m条边之后，先判断是有存在圈。然后在计算每一个点对的连通性。最后对读进来的p场比赛的结果进行判断和统计。

代码：


{{{
#!cpp
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;


const int maxn=1100;
vector<int> E[maxn];
int v[maxn];
int score[maxn];
int d[maxn];
int g[maxn][maxn];
int gg[maxn][maxn];
int w[maxn];


int main(){
    int t =0;
    int n,m;
    while ( scanf("%d%d",&n,&m)!=EOF ) {
        if ( t ) printf("\n");
        ++t;
        memset(d,0,sizeof(d));      
        map<string,int> id;
        vector<string> ans;
        vector<string> name;
        memset(w,0,sizeof(w));
        for(int i=0;i<maxn;++i)E[i].clear();
        int cnt=0;
        memset(g,0,sizeof(g));
        for(int i=0;i<m;++i){
            char s1[20],s2[20];
            scanf("%s%s",s1,s2);
            int &a = id[string(s1)];
            int &b = id[string(s2)];
            if ( a == 0 ) {
                a = ++cnt;
                name.push_back(string (s1));
            }

            if ( b == 0 ) {
                b = ++cnt;
                name.push_back(string (s2));
            }
            char result[100];
            scanf("%s",result);
            if ( *result == 'w' ) {
                E[a].push_back(b);
                ++d[b];
                g[a][b] = 1; 
                ++w[a];
            }
            else {
                ++w[b];
                E[b].push_back(a);
                ++d[a];
                g[b][a] =1 ;
            }
        }

        memset(v,0,sizeof( v));
        int flag = 1 ; 
        int l[maxn];
        for(int i=0;i<n && flag;++i){
            int k; 
            flag = 0 ;
            for(int j=1;j<=n;++j) if ( !v[j] && d[j] == 0 )  {
                k = j ;
                flag= 1;
                break;
            }
            if ( !flag ) break;
            v[k]=1;
            for(int j=0;j<E[k].size();++j){
                d[E[k][j]] -- ;
            }
            l[i]=k;
        }


        if ( flag ) {
            memset(gg,0,sizeof(gg));        
            for(int i=n-1;i>=0;--i){
                for(int j=i+1;j<n;++j)if ( g[l[i]][l[j]]) {
                    gg[l[i]][l[j]] = 1; 
                    for(int k=j+1;k<n;++k) if ( gg[l[j]][l[k]] ) {
                        gg[l[i]][l[k]]= 1; 
                    }

                }
            }



            int p ;
            scanf("%d" , &p ) ; 
            while ( p -- ) {
                char s1[20] , s2[20]; 
                scanf("%s%s",s1,s2);
                int &a = id[string(s1)];
                int &b = id[string(s2)];
                if ( gg[a][b] ) {
                    w[a] ++ ; 
                }
                else if ( gg[b][a] ) {
                    w[b] ++ ; 
                }
                else {
                    flag = 0 ;
                }
            }
            if ( !flag ) {
                printf("Can't judge.\n");
            }
            else {

                int tmp=0;
                for(int i=1;i<=n;++i){
                    if ( w[i] > tmp ) tmp = w[i]; 
                }
                for(int i=1;i<=n;++i){
                    if (w[i]==tmp ) {
                        ans.push_back(name[i-1]);
                    }
                }
                sort(ans.begin(),ans.end());
                for(int i=0;i<ans.size();++i){
                    printf("%s\n" ,ans[i].c_str());
                }
            }
        }
        else {
            int p ; 
            scanf("%d", &p ) ; 
            while ( p -- ) {
                char s1[20] , s2[20 ] ;
                scanf("%s%s", s1 , s2 ) ; 
            }
            printf("Stupid Hiroshi.\n");
        }

    }
    return 0;
}


}}}

题目的意思是，有n个人要进行比赛，现在已经比了m场胜负关系已知的比赛，其中胜负关系是具有传递性的，就是说，如果A胜B，B胜C，那么如果有A和C的比赛，一定是A胜C，否则这个记录就是错的。

接下来还有P场没有记录的比赛，其中比赛的结果要用已经知道的m场的胜负关系推断出来，如果任何一场不能判断，就输出"Can't judge."

这题的做法就是把胜负关系看成有向图的边，读进来m条边之后，先判断是有存在圈。然后在计算每一个点对的连通性。最后对读进来的p场比赛的结果进行判断和统计。

代码：

#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1100;
vector<int> E[maxn];
int v[maxn];
int score[maxn];
int d[maxn];
int g[maxn][maxn];
int gg[maxn][maxn];
int w[maxn];
int main(){
    int t =0;
    int n,m;
    while ( scanf("%d%d",&n,&m)!=EOF ) {
        if ( t ) printf("\n");
        ++t;
        memset(d,0,sizeof(d));      
        map<string,int> id;
        vector<string> ans;
        vector<string> name;
        memset(w,0,sizeof(w));
        for(int i=0;i<maxn;++i)E[i].clear();
        int cnt=0;
        memset(g,0,sizeof(g));
        for(int i=0;i<m;++i){
            char s1[20],s2[20];
            scanf("%s%s",s1,s2);
            int &a = id[string(s1)];
            int &b = id[string(s2)];
            if ( a == 0 ) {
                a = ++cnt;
                name.push_back(string (s1));
            }
            if ( b == 0 ) {
                b = ++cnt;
                name.push_back(string (s2));
            }
            char result[100];
            scanf("%s",result);
            if ( *result == 'w' ) {
                E[a].push_back(b);
                ++d[b];
                g[a][b] = 1; 
                ++w[a];
            }
            else {
                ++w[b];
                E[b].push_back(a);
                ++d[a];
                g[b][a] =1 ;
            }
        }
        memset(v,0,sizeof( v));
        int flag = 1 ; 
        int l[maxn];
        for(int i=0;i<n && flag;++i){
            int k; 
            flag = 0 ;
            for(int j=1;j<=n;++j) if ( !v[j] && d[j] == 0 )  {
                k = j ;
                flag= 1;
                break;
            }
            if ( !flag ) break;
            v[k]=1;
            for(int j=0;j<E[k].size();++j){
                d[E[k][j]] -- ;
            }
            l[i]=k;
        }
        if ( flag ) {
            memset(gg,0,sizeof(gg));        
            for(int i=n-1;i>=0;--i){
                for(int j=i+1;j<n;++j)if ( g[l[i]][l[j]]) {
                    gg[l[i]][l[j]] = 1; 
                    for(int k=j+1;k<n;++k) if ( gg[l[j]][l[k]] ) {
                        gg[l[i]][l[k]]= 1; 
                    }
                }
            }
            int p ;
            scanf("%d" , &p ) ; 
            while ( p -- ) {
                char s1[20] , s2[20]; 
                scanf("%s%s",s1,s2);
                int &a = id[string(s1)];
                int &b = id[string(s2)];
                if ( gg[a][b] ) {
                    w[a] ++ ; 
                }
                else if ( gg[b][a] ) {
                    w[b] ++ ; 
                }
                else {
                    flag = 0 ;
                }
            }
            if ( !flag ) {
                printf("Can't judge.\n");
            }
            else {
                int tmp=0;
                for(int i=1;i<=n;++i){
                    if ( w[i] > tmp ) tmp = w[i]; 
                }
                for(int i=1;i<=n;++i){
                    if (w[i]==tmp ) {
                        ans.push_back(name[i-1]);
                    }
                }
                sort(ans.begin(),ans.end());
                for(int i=0;i<ans.size();++i){
                    printf("%s\n" ,ans[i].c_str());
                }
            }
        }
        else {
            int p ; 
            scanf("%d", &p ) ; 
            while ( p -- ) {
                char s1[20] , s2[20 ] ;
                scanf("%s%s", s1 , s2 ) ; 
            }
            printf("Stupid Hiroshi.\n");
        }
    }
    return 0;
}