首页 > 代码库 > POJ3660 传递闭包———floyd算法
POJ3660 传递闭包———floyd算法
POJ3660 Cow Contest
题目链接:http://poj.org/problem?id=3660
题意:农名约翰有些奶牛,约翰通过让他们决斗来决定他们的排名,约翰让这些奶牛一对一打完一定的局数之后,问有哪些奶牛的排名是可以确定的(注:a打得过b,b打得过c,则a打得c)
根据题意我们明白当一个奶牛和其他的所有奶牛都存在胜负关系的时候,他的排名就是确定的。
思路:利用floyd算法,传递闭包,算出可达矩阵。然后在每一行去查询该点和其他所有的点的联系是不是n-1。
代码:
//Author: xiaowuga #include<iostream> #include<cstring> #include<vector> #include<queue> #define maxx INT_MAX #define minn INT_MIN #define inf 0x3f3f3f3f const long long N=110; using namespace std; typedef long long LL; int n,m; int p[N][N]={0}; void floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) p[i][j]=p[i][j]||p[i][k]&&p[k][j]; } int main(){ cin>>n>>m; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; p[a][b]=1; } floyd(); int ct=0; for(int i=1;i<=n;i++){ int c=0; for(int j=1;j<=n;j++){ if(i==j) continue; if(p[i][j]||p[j][i]) c++; } if(c==n-1) ct++; } cout<<ct<<endl; return 0; }
POJ3660 传递闭包———floyd算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。