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