【USACO】2008 Jan Cow Contest 奶牛比赛

Cow Contest 奶牛比赛

• Description

约翰家有 N 头奶牛正在参加编程比赛，比赛已经进行了 M 轮。在每轮比赛里，会有两头奶牛 PK，在第 i 轮比赛里，第 Ai 头奶牛和第 Bi 头进行比赛，最后 Ai 战胜了 Bi。假设这些比赛完全不 靠运气，也就是说，实力高的奶牛一定会在比赛中胜出（每头奶牛的实力都是不等的）。约翰想搞个 奶牛实力排名榜，但因为比赛次数还不够多，所以一些奶牛的名次还不确定。请帮助他统计一下，以 目前公布的成绩来看，多少奶牛的名次是可以确定的。保证公布的成绩中间不会有矛盾的结果出现。

• Input Format

第一行：两个整数 N 和 M，1 ≤ N ≤ 100; 1 ≤ M ≤ 4500
第二行到第 N + 1 行：第 i + 1 行有两个整数 Ai 和 Bi，1 ≤ Ai;Bi ≤ N

• Output Format

单个整数：表示有多少奶牛的实力名次是确定的

• Sample Input

5 5
4 3
4 2
3 2
1 2
2 5

• Sample Output

2

• Hint

第二头奶牛一定是第四名，第五头奶牛一定是最后一名，其余三头的名次不定

• 分析

如果一头奶牛的名次是一定的，相当于他前面有多少人，后面有多少人也是确定的，而且相加等于n-1。所以我们建完有向图后，先顺着边走，再逆着边走，如果所到达的点有n-1个，则名次就确定了。
据说还有一种Floyd的做法。因为Floyd是枚举中间点k，所以如果i→k且k→j，说明i→j，计算一下出度和入度即可。

• 图遍历

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 101
#define M 4501
using namespace std;
int tot,Ans,n,m,u,v,Last[N],F[N],G[N],Vis[N];
struct Data{int to,next;}E[2*M];
void Addline(int u,int v){
    E[++tot].to=v; E[tot].next=Last[u]; Last[u]=tot;
}
void Dfs(int fa,int u){
    F[u]=1;
    for (int i=Last[u];i;i=E[i].next){
        if (Vis[E[i].to]) continue;
        Vis[E[i].to]=1;
        Dfs(u,E[i].to);
        F[u]+=F[E[i].to],G[E[i].to]++;
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        Addline(u,v);
    }
    for (int i=1;i<=n;i++){
        memset(Vis,0,sizeof(Vis));
        memset(F,0,sizeof(F));
        Dfs(0,i);
        G[i]+=F[i];
    }
    for (int i=1;i<=n;i++)
        if (G[i]==n) Ans++;
    printf("%d",Ans);
    fclose(stdin); fclose(stdout);
    return 0;
}

• Floyd

#include<cstdio>
#include<cstring>
#include<algorithm>
int n,m,x[105],y[105],a,b,ans;bool f[105][105];
int main()
{
    scanf("%d%d", &n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        f[a][b]=true;x[a]++;y[b]++;
    }
    for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    {
        if(!f[i][j])
        if((f[k][j])&&(f[i][k]))    
        {
            f[i][j]=true;x[i]++;y[j]++; 
        }
    }
    for(int i=1;i<=n;++i)
    if(x[i]+y[i]==n-1)ans++;
    printf("%d",ans);   
}
//by zjl

最后

以上就是诚心小懒虫为你收集整理的【USACO】2008 Jan Cow Contest 奶牛比赛的全部内容，希望文章能够帮你解决【USACO】2008 Jan Cow Contest 奶牛比赛所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。