【传递闭包】奶牛的比赛

50 阅读 0 评论 33 点赞

我是靠谱客的博主糟糕世界，最近开发中收集的这篇文章主要介绍【传递闭包】奶牛的比赛，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1、奶牛的比赛（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)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

【输入格式】

第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的奶牛输给了编号为1、3、4的奶牛，也就是说她的水平比这3头奶牛都差。而编号为5的奶牛又输在了她的手下，也就是说，她的水平比编号为5的奶牛强一些。于是，编号为2的奶牛的排名必然为第4，编号为5的奶牛的水平必然最差。其他3头奶牛的排名仍无法确定。

但是脑子抽了，一下子打错方向，就把问题越想越复杂。

一开始想是不是，对于点i，所有的除了点i外的点j都与它有直接相连的边，才能满足条件。

但是后来发现这只是个充分条件，但是并不是必要条件。

后来又想是不是这个点按边遍历可以到达所有出度为0的点，且所有入度为0的点都能遍历到这个点区就满足条件。

后来又发现这又只是一个必要条件，并不充分。

后来又想是不是求割点集，去掉这个点，任意的入度为0的点都不能到达任意出度为0的点。自以为没有漏洞了，结果严重超时。

实际上就和一开始的思路比较接近，确实是所有点都可以由i到达或者到达i，但是不必直接相连。因为传递闭包的模型，在这里体现的含义就是，i比j优，j比k优，则i比k优，但是我们需要知道的不是优劣关系，而仅仅是哪些点之间的关系已经能够确定。

#include <cstdio>
#include <string>
#include <cstring>

bool f[120][120];

long getint()
{
	long rs=0;bool sgn=1;char tmp;
	do tmp = getchar();
	while (!isdigit(tmp)&&tmp!='-');
	if (tmp=='-'){tmp=getchar();sgn=0;}
	do rs=(rs<<3)+(rs<<1)+tmp-'0';
	while (isdigit(tmp=getchar()));
	return sgn?rs:-rs;
}

int main()
{
	freopen("contest.in","r",stdin);
	freopen("contest.out","w",stdout);

	long n = getint();
	long m = getint();

	for (long i=1;i<m+1;i++)
	{
		long a = getint();
		long b = getint();

		f[a][b] = true;
	}
	
	for (long i=1;i<n+1;i++)
		f[i][i] = true;

	for (long k=1;k<n+1;k++)
	{
		for (long i=1;i<n+1;i++)
		{
			if (i == k) continue;
			for (long j=1;j<n+1;j++)
			{
				if (j == k||j == i) continue;
				f[i][j] |= (f[i][k]&&f[k][j]);
			}
		}
	}

	long ans = 0;

	for (long i=1;i<n+1;i++)
	{
		bool ok = true;
		for (long j=1;j<n+1;j++)
		{
			if (!f[i][j] && !f[j][i])
			{
				ok = false;
				break;
			}
		}
		if (ok)
		{
			ans ++;
		}
	}

	printf("%ld",ans);

	return 0;
}