[最短路徑]USACO Jan08 奶牛的比賽 contest 解題報告

【問題描述】
FJ的N(1 <= N <= 100)頭奶牛們最近參加了場程序設計競賽:)。在賽場上，奶牛們按1..N依次編號。每頭奶牛的編程能力不盡相同，並且沒有哪兩頭奶牛的水平不相上下，也就是說，奶牛們的編程能力有明確的排名。

整個比賽被分成了若干輪，每一輪是兩頭指定編號的奶牛的對決。如果編號爲A的奶牛的編程能力強於編號爲B的奶牛(1 <= A <= N; 1 <= B <= N; A != B)，那麼她們的對決中，編號爲A的奶牛總是能勝出。

FJ想知道奶牛們編程能力的具體排名，於是他找來了奶牛們所有M(1 <= M <= 4,500)輪比賽的結果，希望你能根據這些信息，推斷出儘可能多的奶牛的編程能力排名。比賽結果保證不會自相矛盾。

程序名: contest

輸入格式:

第1行: 2個用空格隔開的整數：N 和 M

第2..M+1行: 每行爲2個用空格隔開的整數A、B，描述了參加某一輪比賽的奶牛的編號，以及結果（編號爲A，即爲每行的第一個數的奶牛爲勝者）

輸入樣例 (contest.in):

5 5

4 3

4 2

3 2

1 2

2 5

輸出格式:

第1行: 輸出1個整數，表示排名可以確定的奶牛的數目

輸出樣例 (contest.out):

2

輸出說明:

編號爲2的奶牛輸給了編號爲1、3、4的奶牛，也就是說她的水平比這3頭奶牛都差。而編號爲5的奶牛又輸在了她的手下，也就是說，她的水平比編號爲5的奶牛強一些。於是，編號爲2的奶牛的排名必然爲第4，編號爲5的奶牛的水平必然最差。其他3頭奶牛的排名仍無法確定。

【分析】

圖論的最短路徑問題。開一個二維表Mat[i][j]，初始化為-1。讀入時按有向圖讀入，然後使用Floyd算法求圖的最短路，最後，判斷每個人與其餘人的關係如何。只要與一個人關於不確定，即兩節點的權值為-1，則這個人不能確定，最後只需要輸出能確定的人數即可。

我的同學PaulInsider也做了這個題，看看他的解題報告吧：http://paulinsider.at.ua/news/2011-11-06-4

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int  N,M;
int Mat[101][101];

void init()
{
    scanf("%d %d\n",&N,&M);
   
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            Mat[i][j]=-1;
   
    for (int i=1;i<=N;i++)
        Mat[i][i]=0;
   
    int a,b;
    for (int i=1;i<=M;i++)
    {
        scanf("%d %d\n",&a,&b);
        Mat[a][b]=1;
    }
}

void Floyd()
{
    int tmp;
    for (int k=1;k<=N;k++)
    {
        for (int i=1;i<=N;i++)
        {
            for (int j=1;j<=N;j++)
            {
                if(Mat[i][k]==-1 || Mat[k][j]==-1)
                    continue;
                tmp=Mat[i][k]+Mat[k][j];
                if(tmp<Mat[i][j] || Mat[i][j]==-1)
                    Mat[i][j]=tmp;
               
            }
        }
    }
}

void search()
{
    int S=0; 
    for (int i=1;i<=N;i++)
    {
        bool flag=true;
        for (int j=1;j<=N;j++)
        {
            if(Mat[i][j]==-1 && Mat[j][i]==-1)
            {
                flag=false;
                break;
            }
        }
        if(flag)
            S++;
    }
    printf("%d\n",S);
}

int main()
{
    freopen("contest.in","r",stdin);
    freopen("contest.out","w",stdout);
    init();
    Floyd();
   
    /*
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=N;j++)
            cout<<Mat[i][j]<<" ";
        cout<<endl;
    }*/
   
    //cout<<endl;
    search();
    return 0;
}

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	312 KB	0
2	正确	10	0.006 s	312 KB	0
3	正确	10	0.000 s	312 KB	0
4	正确	10	0.000 s	312 KB	0
5	正确	10	0.000 s	312 KB	0
6	正确	10	0.001 s	312 KB	0
7	正确	10	0.001 s	312 KB	0
8	正确	10	0.002 s	312 KB	0
9	正确	10	0.004 s	312 KB	0
10	正确	10	0.006 s	312 KB	0

运行完成
运行时间 0.021 s
平均内存使用 312 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
返回原题