POJ|POJ - 3660 Cow Contest 传递闭包floyed算法 POJ-3660CowContest传递闭包floyed算

Cow Contest POJ - 3660 ：http://poj.org/problem?id=3660
参考： https://www.cnblogs.com/kuangbin/p/3140837.html 题意： n头牛，有m对牛进行了比赛，现在告诉你每队牛比赛的结果，A胜B，问有几头牛的排名可以确定。
思路：题目给出了m对的相对关系，求有多少个排名是确定的。
使用floyed求一下传递闭包。如果这个点和其余的关系都是确定的，那么这个点的排名就是确定的。

文章图片

文章图片

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //#pragma GCC optimize(3) //#pragma comment(linker, "/STACK:102400000,102400000")//c++ #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << "\n"; #define pb push_back #define pq priority_queuetypedef long long ll; typedef unsigned long long ull; typedef pair pll; typedef pair pii; typedef pair p3; //priority_queue q; //这是一个大根堆q //priority_queue,greater >q; //这是一个小根堆q #define fi first #define se second //#define endl '\n'#define OKC ios::sync_with_stdio(false); cin.tie(0) #define FT(A,B,C) for(int A=B; A <= C; ++A)//用来压行 #define REP(i , j , k)for(int i = j ; i , greater >que; const ll mos = 0x7FFFFFFF; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; const double PI=acos(-1.0); template inline T read(T&x){ x=0; int f=0; char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; }/*-----------------------showtime----------------------*/ const int maxn = 120; int mp[maxn][maxn]; int main(){ int n,m; scanf("%d%d", &n, &m); for(int i=1; i<=m; i++){ int u,v; scanf("%d%d", &u, &v); mp[u][v] = 1; } for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ mp[i][j] = (mp[i][j] || (mp[i][k] && mp[k][j])); } } } int ans = 0,cnt; for(int i=1; i<=n; i++){ cnt = 0; for(int j=1; j<=n; j++){ if(mp[i][j] || mp[j][i])cnt++; } if(cnt>=n-1)ans++; } printf("%d\n", ans); return 0; }