题目描述

cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.
The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (), then cow A will always beat cow B.
Farmer John is trying to rank the cows by skill level. Given a list the results of two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

输入描述:

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B

输出描述:

* Line 1: A single integer representing the number of cows whose ranks can be determined

示例1

输入
5 5
4 3
4 2
3 2
1 2
2 5

输出
2
说明
Cow 2 loses to cows 1, 3, and 4. Thus, cow 2 is no better than any of the cows 1, 3, and 4. Cow 5 loses to cow 2, so cow 2 is better than cow 5. Thus, cow 2 must be fourth, and cow 5 must be fifth. The ranks of the other cows cannot be determined.

解答

这道题很明显有传递性（即a赢b，b赢c，则a赢c，相反，a输b，b输c，则a输c）
我们设两个型二维数组和，其中表示赢，即的实力比强，表示输，即的实力比弱，一边输入，可以一边初始化和
输入代码： 
n=read();m=read();
for(i=1;i<=m;i++){
    a=read();b=read();
    w[a][b]=true;l[b][a]=true;
}
其中read()为读入优化（听说每500万个数据可省100毫秒）
读入优化代码（需要调用cctype库）： 
#define g(c) isdigit(c)
#define gc getchar()
int read(){
    char c=0;int x=0,f=0;
    while (!g(c)) f|=c=='-',c=gc;
    while (g(c)) x=x*10+c-48,c=gc;
    return f?-x:x;
}

然后，我们对w和l数组分别进行一次floyd算法（n不大，能过）

floyd算法代码： 

void floyd(bool f[N][N]){
    //注意不能写成floyd(bool f[][])，会CE(编译错误)
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    if (i!=k)
    for(int j=1;j<=n;j++)
    if (j!=i&&j!=k)
    f[i][j]=f[i][j]||(f[i][k]&&f[k][j]);
}
//因为floyd算法要进行两遍且两遍代码几乎一样
//所以我们可以把floyd算法定义为一个函数，而非直接打两遍几乎一样的代码
int main(){
    读入+预处理
    floyd(w);floyd(l);
}
最后，我们对于每个，枚举，若或，我们把计算器s++,若则答案，输出ans程序结束
因为时，肯定等于（即不可能赢，倒回来又赢），同理时，肯定等于，所以不会出现少算或多算
实际测试中和肯定等于，所以和不必判断是否相等 
for(i=1;i<=n;i++){
    for(j=1,s=0;j<=n;j++)
    if (w[i][j]) s++;
    for(j=1;j<=n;j++)
    if (l[i][j]) s++;
    if (s==n-1) ans++;
}
printf("%d",ans);
完整代码： 
#include <bits/stdc++.h>
using namespace std;
const int N=105;
bool w[N][N],l[N][N];
int n,m,a,b,i,j,s,ans;
#define g(c) isdigit(c)
#define gc getchar()
int read(){
    char c=0;int x=0,f=0;
    while (!g(c)) f|=c=='-',c=gc;
    while (g(c)) x=x*10+c-48,c=gc;
    return f?-x:x;
}
void floyd(bool f[N][N]){
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    if (i!=k)
    for(int j=1;j<=n;j++)
    if (j!=i&&j!=k)
    f[i][j]=f[i][j]||(f[i][k]&&f[k][j]);
}
int main(){
//  freopen("t2.in","r",stdin);
    n=read();m=read();
    for(i=1;i<=m;i++){
        a=read();b=read();
        w[a][b]=true;l[b][a]=true;
    }
    //读入+预处理
    floyd(w);floyd(l);
    //floyd算法
    for(i=1;i<=n;i++){
        for(j=1,s=0;j<=n;j++)
        if (w[i][j]) s++;
        for(j=1;j<=n;j++)
        if (l[i][j]) s++;
        if (s==n-1) ans++;
    }
    //计算结果
    printf("%d",ans);
    return 0;
}
最后，说一下万能头bits/stdc++.h
noi比赛文件中说：理论上可以用万能头，但实际中可能不支持使用万能头，若因为使用万能头而导致CE（编译错误），比赛概不负责，即选手负全责！！！
所以，比赛时建议不要使用万能头，平时可以稍微使用一下


来源：少年更应学习，将来为祖国奋斗！