【POJ-3660】解题报告（Floyd传递闭包）

原始题目

Cow Contest

  • Time Limit: 1000MS
  • Memory Limit: 65536K
  • Total Submissions: 15815
  • Accepted: 8813

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

Source

USACO 2008 January Silver

题目大意

一共有N头牛，现在知道M条信息，每条信息描述两头牛谁更强一些，问可以确定最多多少头牛的排名。

解题思路

  • 还在学习中，使用Floyd算法求闭包，（A胜B，B胜C，则传递A胜C）
  • 然后对于每头牛扫一遍是否与其他n-1头牛都有确定的胜负关系，如果有的话答案++。
  • 还需要深入学习Floyd算法

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#define mp make_pair
#define pb push_back
#define np next_permutation
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define first fi
#define second se
#define eps 1e-9
#define INF 0x3f3f3f3f
#define ms(x,a) memset((x),a,sizeof((x)))
#define all(x) x.begin(),x.end()
#define gapline cout<<"##================##"<<endl
using namespace std;
const int maxn=1e3+5;
const int mal=26;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
bool ans[maxn][maxn];
	int n,m;
void Floyd(){
	rep(k,1,n+1)
		rep(i,1,n+1)
			rep(j,1,n+1)
				ans[i][j]=ans[i][j]|(ans[i][k]&ans[k][j]); 
}
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n){
		cin>>m;
		ms(ans,0);
		rep(i,0,m){
			int a,b;
			cin>>a>>b;
			ans[a][b]=1;
		}
		Floyd();
		int aans=0;
		rep(i,1,n+1){
			int ccnt=0;
			rep(j,1,n+1){
				if(ans[i][j]||ans[j][i]) ccnt++;
			}
			if(ccnt==n-1) aans++; 
		}
		cout<<aans<<endl;
	} 
}

收获与反思

  • 挖坑，加强理解Floyd最短路算法。