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\) ，描述了参加某一轮比赛的奶牛的编号，以及结果（每行的第一个数的奶牛为胜者）。
输出
输出一行一个整数，表示排名可以确定的奶牛的数目。
样例
5 5
4 3
4 2
3 2
1 2
2 5
2
解释
编号为 \(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();
}