POJ 3660 Cow Contest （最短路弗洛伊德）

65 阅读 0 评论 43 点赞

我是靠谱客的博主仁爱帆布鞋，最近开发中收集的这篇文章主要介绍POJ 3660 Cow Contest （最短路弗洛伊德），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【题目链接】
http://poj.org/problem?id=3660

题目意思

有一群等级从1到n的牛比赛，现在告诉你m次比赛结果A B（A大于B），问你能确定某牛等级的只数。

解题思路

某头牛能确定和其他n-1头牛的关系就能确定自己的等级。（只要确定几胜几负就可以了，当胜数加负数等于n-1，那么这只牛的等级一定为负数加1）。所以用弗洛伊德把两两关系求出。在判断有多只是可以确定等级的。

代码部分


#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <string>
#include <map>
using namespace std;
#define LL long long
#define inf 0x3f3f3f3
const int N = 105;
int n,m;
int maps[N][N];
int main()
{
while (~scanf("%d %d",&n,&m))
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
maps[i][j] = inf;
}
}
for (int i = 1; i <= m; i++)
{
int u,v;
scanf("%d %d",&u,&v);
maps[u][v] = 1;
///u大于v 
maps[v][u] = -1;
/// v小于u 
}
for (int j = 1; j <= n; j++)
///利用点j缩点 
for (int i = 1; i <= n; i++)
for (int k = 1; k <= n; k++)
///对战关系嫁接 
{
if (maps[i][j] == maps[j][k] && maps[i][j] !=inf)
maps[i][k] = maps[i][j];
}
int ans = 0;
for (int i = 1; i <= n ; i++)
{
bool fa = true;
for (int j = 1; j <= n; j++)
{
if (i == j)
continue;
if (maps[i][j] == inf)
{
fa = false;
break;
}
}
if (fa)
ans++;
}
printf("%dn",ans);
}
return 0;
}