Zhao70's Blog

POJ3660 Cow Contest

发表于 | 分类于

题目大意

POJ3660 Cow Contest

n 只牛之间进行比赛, 给定 m 条关于两只牛之间的强弱信息, 求有多少只牛排名确定.

思路

若对于任意一只牛, 若知道比它排名高的牛有 x 只, 比它排名低的牛有 y 只, x + y == n - 1. 则可以知道这头牛的排名.

利用 Floyd-Warshall, 求出图中的传递闭包, 若一个点与其他所有点的关系已知, 则可以求解这个点的排名.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
const int arrSize = 110;
bool edge[arrSize][arrSize];
int main(){
    int nVertex, nEdge;
    cin >> nVertex >> nEdge;
    for(int i = 0; i < nEdge; i++){
        int a, b;
        cin >> a >> b;
        edge[a][b] = true;
    }
    for(int k = 1; k <= nVertex; ++k){
        for(int i = 1; i <= nVertex; ++i){
            for(int j = 1; j <= nVertex; ++j){
                if(edge[i][k] && edge[k][j])
                    edge[i][j] = true;
            }
        }
    }
    int cnt = 0;
    for(int i = 1; i <= nVertex; ++i){
        bool flag = true;
        for(int j = 1; j <= nVertex; ++j){
            if(i == j)
                continue;
            if(edge[i][j] == false && edge[j][i] == false){
                flag = false;
                break;
            }
        }
        if(flag)
            cnt++;
    }
    cout << cnt;
    return 0;
}