P2419 Cow Contest S

8个月前更新

480

Cow Contest S

此题链接

题目

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

输入

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

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

输出

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

样例

解释

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

法一 : dfs

思路

要确定一头牛的位置，即要知道前面有$a$头牛，后面有（n – a – 1）头牛
用两个图来存，一个图$gw$存放所有获胜过的牛，另一个图$gl$存放所有失败过的牛

依次dfs得到比x强的牛，比x强的牛还要强的牛…..记录个数sw
依次dfs得到比x弱的牛，比x弱的牛还要弱的牛…..记录个数sl

如果$sw + sl == n – 1$，则$cnt++$

代码

点击

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
#include <vector>
#include <cstring>
#include <bitset>

using namespace std;
using ll = long long;
const int N = 5e3;
int n, m, sw, sl, stw[N], stl[N];
vector<int> gw[N], gl[N];

int gcd(int a, int b)
{
	if(b == 0) return a;
	else return gcd(b, a % b);
}
bool cmp(int a, int b) {return a > b;}

void dfsw(int x) { //dfs所有比x强的来得到sw
	for(int u : gw[x]) {
		if(!stw[u]) { //如果之前的递归中u没有出现过，则多了一个比x强的
			sw++;
			stw[u] = 1;
			dfsw(u); //看有没有比u强的。u比x强，即比u强的也比x强
		}
	}
}

void dfsl(int x) { //dfs所有比x弱的来得到sl
	for(int u : gl[x]) {
		if(!stl[u]) {
			sl++;
			stl[u] = 1;
			dfsl(u);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int cnt = 0;
	for(int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		gw[b].push_back(a); //记录相对于b的所有胜者
		gl[a].push_back(b); //记录相对于a的所有败者
	}
	for(int i = 1; i <= n; i++) {
		sw = 0, sl = 0; //sw比i强的, sl是比i弱的
		memset(stw, 0, sizeof stw);
		memset(stl, 0, sizeof stl);
		dfsw(i), dfsl(i);
		if(sw + sl == n - 1) cnt++; //如果n-1个位置都能确定，那么成立
	}
	cout << cnt;
}

法二 : floyd

思路

传递闭包 ：通过传递性推断出多个元素之间的关系
如果$i$ 和 $j$ 能够建立直接关系$f[i][j] = 1$ 或者 通过桥梁 $k$ 建立间接关系 $f[i][k] = 1 , f[k][j] = 1$，那么$i$ 和 $ j$ 之间有关系
如果$i$ 和 $n – 1$个数都有关系，那么符合条件

代码

点击

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
#include <vector>
#include <cstring>
#include <bitset>

using namespace std;
using ll = long long;
const int N = 110;
int f[N][N], n, m;

int gcd(int a, int b)
{
	if(b == 0) return a;
	else return gcd(b, a % b);
}
bool cmp(int a, int b) {return a > b;}

void solve() {
	int n, m; cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		f[a][b] = 1;
	}
	for(int k = 1; k <= n; k++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) 
				f[i][j] |= f[i][k] & f[k][j];
				//如果i和j具有直接输赢i>j, 或者以k作为桥梁i>k>j, 那么i和j能确定输赢关系
		}
	}
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		int cnt = 1; //cnt为是否能建立关系
		for(int j = 1; j <= n; j++) 
		//自己和自己不用管, 所以i != j时
			if(i != j) cnt = cnt & (f[i][j] | f[j][i]);
			//遍历所有点, 看是否除i以外的点都和i有关系
			//如果有一个i和j无关, 那么cnt = 0, 后面循环的cnt则都为0
		sum += cnt; //如果i能做到, sum自增
	}
	cout << sum;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
}

来源链接：https://www.cnblogs.com/PeachyGalaxy/p/18678852/0118p

评分

欢迎为Ta评分