P2419 [USACO08JAN]Cow Contest S-Toy模板网

这篇具有很好参考价值的文章主要介绍了P2419 [USACO08JAN]Cow Contest S。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

�(1≤�≤100)N(1≤N≤100) cows, conveniently numbered 1 �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 �(1≤�≤�;1≤�≤�;�≠�)B(1≤A≤N;1≤B≤N;A=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 �(1≤�≤4,500)M(1≤M≤4,500) 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.

FJ的 �N（1≤�≤1001≤N≤100）头奶牛们最近参加了场程序设计竞赛。在赛场上，奶牛们按 1,2,⋯ ,�1,2,⋯,N 依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为 �A 的奶牛的编程能力强于编号为 �B 的奶牛（1≤�,�≤�1≤A,B≤N，�≠�A=B)，那么她们的对决中，编号为 �A 的奶牛总是能胜出。 FJ 想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 �M（1≤�≤4,5001≤M≤4,500）轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

输入格式

第一行两个用空格隔开的整数 �,�N,M。

第 2∼�+12∼M+1 行，每行为两个用空格隔开的整数 �,�A,B ，描述了参加某一轮比赛的奶牛的编号，以及结果（每行的第一个数的奶牛为胜者）。

输出格式

输出一行一个整数，表示排名可以确定的奶牛的数目。

输入输出样例

输入 #1复制
5 5
4 3
4 2
3 2
1 2
2 5
输出 #1复制
2
说明/提示

样例解释：

编号为 22 的奶牛输给了编号为 1,3,41,3,4 的奶牛，也就是说她的水平比这 33 头奶牛都差。而编号为 55 的奶牛又输在了她的手下，也就是说，她的水平比编号为 55 的奶牛强一些。于是，编号为 22 的奶牛的排名必然为第 44，编号为 55 的奶牛的水平必然最差。其他 33 头奶牛的排名仍无法确定。

1.理解题意：用一个n*n的邻接图来存储奶牛们的胜负情况，由于有胜负两种情况，只要一头奶牛跟其他的奶牛有联系不管是胜还是负都可以得到该奶牛在这群奶牛排名的位置。所以在实际操作时，map[i][j]和map[j][i]有一个等于1都可以得到该奶牛和这个奶牛相比的结果。

2.使用Floyd算法，先将奶牛们的情况记录下来，注意其中有一个传递的关系，由于题目中已经说明，每个奶牛的能力不等，所以，如果A赢了B，B赢了C，那么A一定可以赢C。

3.对可以确定位置的奶牛进行计数，计数规则是，该奶牛在图中和其他奶牛有联系不管输赢。

#include"stdio.h"
int map[105][105];
int ans=0;
main()
{
	int n,m,i,j,x,y,k;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		map[x][y]=1;
	} 
	for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		map[i][j]=map[i][j]||(map[i][k]&&map[k][j]);//联通块 
	}
	for(i=1;i<=n;i++)
	{
		int a=1;
		for(j=1;j<=n;j++)
		{
			if(i==j) continue;
		    else a=a&&(map[i][j]||map[j][i]);
			//该奶牛被其他奶牛打赢或者打赢其他奶牛的状态，如果这个奶牛和其他奶牛都有联系则可以判断出它的排名 
		}
		ans+=a;	
	}
	printf("%d\n",ans);
}

文章来源地址https://www.toymoban.com/news/detail-436226.html

到了这里，关于P2419 [USACO08JAN]Cow Contest S的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！