奶牛的比赛(传递闭包)

奶牛的比赛

Description

FJ的N(1≤N≤100) 头奶牛们最近参加了场程序设计竞赛。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。

整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1≤A,B≤N,A̸=B) ，那么她们的对决中，编号为A的奶牛总是能胜出。

FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M(1≤M≤4,500) 轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

Input

• 第1行: 2个用空格隔开的整数：N 和 M
• 第2..M+1行: 每行为2个用空格隔开的整数A、B，描述了参加某一轮比赛的奶 牛的编号，以及结果（编号为A，即为每行的第一个数的奶牛为 胜者）

Output

• 第1行: 输出1个整数，表示排名可以确定的奶牛的数目

Sample Input 1

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

Sample Output 1

2

这个题的考察点是"传递闭包",就是说,如果x优于y,y优于z,那么x优于z

这个东西是很容易用floyd算法实现的,

    for (int k = 1;k <= N; k++){
        for (int i = 1;i <= N; i++){
            for (int j = 1;j <= N; j++){
                if(cost[i][j] == 0&& (cost[i][k] == 1 && cost[k][j] == 1)){
                    cost[i][j] = 1;
                }
            }
        }
    }

就是说,我们可以很容易地根基现有的信息处理出来"谁比谁厉害"这样的结果.

那我怎么判断某一元素的排名是确定的呢?

只要"比我厉害的元素"和"不如我厉害的元素"的和为N-1,就说明目前这个元素的排名是确定的

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;
const int MAX_N = 102;

int cost[MAX_N][MAX_N];
//cost[i][j]==1代表"i比j厉害"

int main(){
    ios::sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= M; i++){
        int a, b;
        cin >> a >> b;
        cost[a][b] = 1;
    }
    for (int k = 1;k<=N; k++){
        for (int i = 1;i<=N; i++){
            for (int j = 1;j<=N; j++){
                if(cost[i][j]==0&&(cost[i][k]==1&&cost[k][j]==1)){
                    cost[i][j] = 1;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1;i<=N; i++){
        int high = 0, low = 0;
        for (int j = 1;j<=N; j++){
            if(cost[j][i]){
                high++;
            }
            if(cost[i][j]){
                low++;
            }
        }
        if(high+low==N-1){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}