POJ3660 Cow Contest {图论}【最短路】（Floyd，传递闭包）

题意

    有$n$头牛， 给你m对关系$(a,b)$表示牛$a$能打败牛$b$， 求在给出的这些关系下， 能确定多少牛的排名。

题解

    先讲一下关系闭包：
    关系闭包有三种： 自反闭包$(r)$， 对称闭包$(s)$， 传递闭包$(t)$。
    先画出$R$的关系图，再画出$r(R)$，$s(R)$，$t(R)$的关系图。
    我们今天用的是传递闭包。仅作为个人理解传递闭包：关系之间具有传递性（例如$a>b$，$b>c$，那么$a>c$），在那些已给出的关系基础上，通过传递性，把所有可能的关系都找出来。
    如果一头牛被$x$头牛打败，并且可以打败$y$头牛，如果$x+y=n-1$，则我们容易知道这头牛的排名就被确定了，所以我们只要将任一头牛，可以打败其他的牛的个数$x$， 和能打败该牛的牛的个数$y$求出来，在遍历所有牛判断一下是否满足$x+y=n-1$，就知道这个牛的排名是否能确定了（而传递闭包，正好将所有能得出关系都求出来了）， 再将满足这个条件的牛数目加起来就是所求解。 $x$可以看成是入度，$y$是出度。
    该段落出处https://www.cnblogs.com/wd-one/p/4545086.html

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
//#include<unordered_map>
#define lowbit(x) ((x) & -(x));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5 + 10, NN = 1e4 + 10, INF = 0x3f3f3f3f, LEN = 110;
const ll MOD = 1e9 + 7;
const ull seed = 31;
int n, m;
int gra[NN][NN];
void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
if (gra[i][k] == INF)
continue;
for (int j = 1; j <= n; j++)
if (gra[k][j] != INF)
gra[i][j] = 1;
}
}
}
void init() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
gra[i][j] = INF;
}
int main() {
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
gra[u][v] = 1;
}
floyd();
int ans = 0;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = 1; j <= n; j++)
if (gra[i][j] == 1 || gra[j][i] == 1)
++sum;
if (sum == n - 1)
++ans;
}
printf("%dn", ans);
}

最后

以上就是长情金针菇为你收集整理的POJ3660 Cow Contest {图论}【最短路】（Floyd，传递闭包）的全部内容，希望文章能够帮你解决POJ3660 Cow Contest {图论}【最短路】（Floyd，传递闭包）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。