1612: [Usaco2008 Jan]Cow Contest奶牛的比賽

Time Limit: 5 Sec Memory Limit: 64 MB

Description

FJ的N(1 <= N <= 100)頭奶牛們最近參加了場程序設計競賽:)。在賽場上，奶牛們按1..N依次編號。每頭奶牛的編程能力不盡相同，并且沒有哪兩頭奶牛的水平不相上下，也就是說，奶牛們的編程能力有明確的排名。 整個比賽被分成了若干輪，每一輪是兩頭指定編號的奶牛的對決。如果編號為A的奶牛的編程能力強于編號為B的奶牛(1 <= A <= N; 1 <= 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

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

Sample Output

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

題解

我們要確定一個人的排名，那么就需要知道他贏誰或輸給誰，只有全部知道是才可以確定，如果有兩個人不確輸贏定，那么就不能確定排名。
所以我們可以Floyd一下，知道i與j的輸贏關系，最后如果i能贏j，那么j一定輸給i，如果出現矛盾，那么就不能確定排名。

代碼如下

#include<cstdio> #include<algorithm> using namespace std; int n,m,Ans,tl=0,hd=0,f[105],dst[105][105]; int main(){#ifndef ONLINE_JUDGEfreopen("prob.in","r",stdin);freopen("prob.out","w",stdout);#endifscanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);dst[x][y]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i^j&&j^k&&k^i) dst[i][j]|=dst[i][k]&&dst[k][j];for(int i=1;i<=n;i++){bool t=1;for(int j=1;j<=n;j++)if(i^j&&dst[i][j]==dst[j][i]){t=0;break;}Ans+=t;}printf("%d\n",Ans);return 0; }

轉載于:https://www.cnblogs.com/XSamsara/p/9043185.html

總結

以上是生活随笔為你收集整理的BZOJ 1612: [Usaco2008 Jan]Cow Contest奶牛的比赛【Floyd】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。