floyd求传递闭包

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

n头牛比赛,m种比赛结果,最后问你一共有多少头牛的排名被确定了,其中如果a战胜b,b战胜c,则也可以说a战胜c,即可以传递胜负。求能确定排名的牛的数目。

思路:如果一头牛被x头牛打败,打败y头牛,且x+y=n-1,则我们容易知道这头牛的排名就被确定了,所以我们只要将任何两头牛的胜负关系确定了,在遍历所有牛判断一下是否满足x+y=n-1,将满足这个条件的牛数目加起来就是所求解。

抽象为简单的floyd传递闭包算法,在加上每个顶点的出度与入度 (出度+入度=顶点数-1,则能够确定其编号)。

传递闭包的定义:

G的传递闭包定义为G*=(V,E*),其中E={(i,j):图G中存在一条从i到j的路径}。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
const int maxn=205;

int n, m;
int e[maxn][maxn]={0};
int s[maxn][2]={0};

void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                e[i][j]=(e[i][j]||(e[i][k]&&e[k][j]));
            }
        }
    }

}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int x, y;
        scanf("%d%d",&x,&y);
        e[x][y]=1;
    }
    floyd();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            s[i][0]+=e[i][j];
            s[j][1]+=e[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i][0]+s[i][1]==n-1)
        {
            ans++;
        }
    }
    cout<<ans<<endl;

    return 0;
}
全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
06-15 18:44
黄淮学院 Java
Lynn012:如果是居民楼还是算了吧,看着有点野呢
点赞 评论 收藏
分享
鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务