POJ-3660 Cow Contest Floyd传递闭包的应用
2024-10-01 14:37:25
题目链接:https://cn.vjudge.net/problem/POJ-3660
题意
有n头牛,每头牛都有一定的能力值,能力值高的牛一定可以打败能力值低的牛
现给出几头牛的能力值相对高低
问在一场一对一的比赛中,那些牛的排名可以确定下来
思路
一开始还以为是topo排序,每次去掉没有入度或出度的节点
若有两个及以上的节点可以去掉,则排序结束
然后写出来WA两发...
正确思路:
若满足x头牛可以打败牛a,牛a可以打败y头牛,且nx+y-1时牛a排名唯一确定
那么可以利用Floyd传递闭包来生成一个数组G[a][b],表示a可以打败b
当$ \sum G[i][a]+G[a][i]n-1$时,可以确定牛a排名
代码
#include <cstring>
#include <cstdio>
const int maxn=100;
bool G[maxn+5][maxn+5]={false};
void Floyd(int n){
for (int k=1; k<=n; k++)
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
G[i][j]=G[i][j] || (G[i][k] && G[k][j]);
}
int main(void){
int n, m, a, b;
memset(G, false, sizeof(G));
scanf("%d%d", &n, &m);
for (int i=0; i<m; i++){
scanf("%d%d", &a, &b);
G[a][b]=true;
}Floyd(n);
int ans=0;
for (int i=1; i<=n; i++){
int cnt=0;
for (int j=0; j<=n; j++) if (i!=j && (G[i][j] || G[j][i]))
cnt++;
if (cnt==n-1) ans++;
}printf("%d\n", ans);
return 0;
}
Time | Memory | Length | Lang | Submitted |
---|---|---|---|---|
32ms | 364kB | 685 | G++ | 2018-05-25 15:05:57 |
最新文章
- GIT本地配置和PUSH
- ES5 Objece.creat实现继承
- Convert.ToInt16 与 Convert.ToInt32 区别
- [zz]论程序员
- uva 1335 - Beijing Guards
- 优化之sitemap+RSS
- 微信 python 接口 -- itchat 文档
- Redis分布式队列和缓存更新
- Git常用命令使用大全
- Python代码缩进与测试模块
- 【调试基础】Part 5 PE格式
- php中测试运行的时间,从而选择得出优化程序
- Linux常用命令之网络和关机重启命令
- CUDA编程之快速入门
- EXCEL中把两列表格里的数字合成一列并且中间用逗号隔开
- vue常用UI组件
- 单字段去重 distinct 返回其他多个字段
- Java - 26 Java 数据结构
- PHP 调试工具Xdebug安装配置
- Android MD5算法
热门文章
- Python介绍与学习
- hive(I)--学习总结之常用技能
- Is jQuery Still Relevant in 2018?
- vue2.0变化(转载)
- docker images镜像无法删除
- NOI 2018 屠龙勇士 (拓展中国剩余定理excrt+拓展欧几里得exgcd)
- 使用tf.ConfigProto()配置Session运行参数和GPU设备指定
- 新手学python-Day4-进制,数据类型,编码转换,列表
- 小学生绞尽脑汁也学不会的python(初识面对对象)
- Git:与eclipse搭配使用