POJ 3660 Cow Contest / HUST 1037 Cow Contest / HRBUST 1018 Cow Contest（图论，传递闭包）

时间：2023-03-08 17:46:29

POJ 3660 Cow Contest / HUST 1037 Cow Contest / HRBUST 1018 Cow Contest（图论，传递闭包）

Description

N (1 ≤ N ≤ 100) 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 (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 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.

Input

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

Output

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

Sample Input

5 5

4 3

4 2

3 2

1 2

2 5

Sample Output

2

Http

POJ:https://vjudge.net/problem/POJ-3660

HUST:https://vjudge.net/problem/HUST-1037

HRBUST:https://vjudge.net/problem/HRBUST-1018

Source

图论，传递闭包

题目大意

给出n只奶牛的m次决斗结果，要求现在能确定多少只奶牛的排名

解决思路

自己一开始yy了好久割点啥的

先看一下题目中要求的，如果一只牛与其他牛确定了的关系n-1，则说明这只牛的排名是确定的，即该牛打赢的牛的数量+该牛打输的牛的数量n-1时此牛的排名是确定的。

但是根据题目中给出的m对决斗结果不能推出所有的情况，这时我们就要利用传递性，牛A打赢了牛B，牛B打赢了牛C，那么牛A也就可以打赢牛C，这个我们可以用类似Floyed算法来解（似乎这个算法有个具体的名称，但博主这里忘记了）。

注意：HRBUST有多组数据

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxN=101;

const int inf=2147483647;

int n,m;

int M[maxN][maxN];

int main()

{

	while (cin>>n>>m)

	{

	memset(M,0,sizeof(M));

	for (int i=1;i<=m;i++)

	{

		int u,v;

		cin>>u>>v;

		M[u][v]=1;

	}

	for (int k=1;k<=n;k++)//传递闭包

		for (int i=1;i<=n;i++)

	    	for (int j=1;j<=n;j++)

	            M[i][j]=M[i][j] || ((M[i][k])&&(M[k][j]));

	int Ans=0;

	for (int i=1;i<=n;i++)

	{

		int cnt=0;

		for (int j=1;j<=n;j++)

		    if ((i!=j)&&((M[i][j])||(M[j][i])))//M[i][j]就是i打赢j，M[j][i]表示i被j打败，因为不管被打败还是打赢，都是确定了i与j的关系，所以都要统计

		        cnt++;

		if (cnt==n-1)

		    Ans++;

	}

	cout<<Ans<<endl;

    }

	return 0;

}

相关文章