题意:有N头牛,M个关系,每个关系A B表示编号为A的牛比编号为B的牛强,问若想将N头牛按能力排名,有多少头牛的名次是确定的。

分析:

1、a[u][v]=1表示牛u比牛v强,flod扫一遍,可以将所有牛的大小关系都存入a。

2、对于每一头牛,cntfront表示比它强的牛的个数,cntrear表示比它弱的牛的个数,若两者相加等于N-1,那该牛的名次自然可以确定。

#pragma comment(linker, "/STACK:102400000, 102400000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define Min(a, b) ((a < b) ? a : b)
#define Max(a, b) ((a < b) ? b : a)
const double eps = 1e-8;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 100 + 10;
const int MAXT = 10000 + 10;
using namespace std;
int a[MAXN][MAXN];
int ans;
int N, M;
int solve(){
for(int i = 1; i <= N; ++i){
int cntfront = 0, cntrear = 0;
for(int j = 1; j <= N; ++j){
if(a[j][i]) ++cntfront;
if(a[i][j]) ++cntrear;
}
if(cntfront + cntrear == N - 1) ++ans;
}
return ans;
}
int main(){
scanf("%d%d", &N, &M);
for(int i = 0; i < M; ++i){
int u, v;
scanf("%d%d", &u, &v);
a[u][v] = 1;
}
for(int k = 1; k <= N; ++k){
for(int i = 1; i <= N; ++i){
for(int j = 1; j <= N; ++j){
if(a[i][k] && a[k][j]) a[i][j] = 1;
}
}
}
printf("%d\n", solve());
return 0;
}

  

最新文章

  1. 洛谷 P1529 回家 Bessie Come Home Label:Dijkstra最短路 &amp;&amp; 乱搞
  2. shell中对字符串的处理
  3. 比较Java数组,ArrayList,LinkedList,Vector 性能比较
  4. 稳定的奶牛分配 &amp;&amp; 二分图多重匹配+二分答案
  5. php二维数组,按照指定的key,去排序value值
  6. 阿里游戏大数据sesson2_RF&amp;amp;GBRT(上)
  7. DxPackNet 2.视频截图和捕捉帧图片
  8. 【android】安卓手机连接电脑了,但是adb devices找不到设备及找到设备但无权限的问题
  9. JavaSE基础知识(5)—面向对象(5.5 this和super关键字)
  10. drawable内存管理
  11. ubuntu 远程登录错误
  12. ASP.NET中HttpApplication中ProcessRequest方法中运行的事件顺序;ASP.NET WebForm和MVC总体请求流程图
  13. MT【27】对数方程组求范围
  14. 《HTTP - http报文》
  15. Codeforces 934D - A Determined Cleanup
  16. Jmeter常用脚本开发之Debug Sampler
  17. mybatis @SelectKey加于不加的区别
  18. 如何在jsp和html页面上获取当前时间
  19. Sql server在另一台服务器,在Visual Studio 中没问题,IIS中 提示“在与 SQL Server 建立连接时出现与网络相关的或特定于实例的错误。。。。”
  20. 多目标跟踪方法 NOMT 学习与总结

热门文章

  1. java 加法变乘法
  2. 小程序通过web-view实现与h5页面之间的交互
  3. 004.Oracle数据库 , 查询多字段连接合并
  4. mysql 结果排序入门
  5. DragonFlyBSD 5.6 RC1 发布
  6. POJ1611 &amp;&amp; POJ2524 并查集入门
  7. 微服务框架中springboot启动的一个问题
  8. 指令——df
  9. Linux 文件夹和文件大小排序
  10. 092-PHP定义索引数组