首页 > 代码库 > shortpath3660

shortpath3660

poj3660_传递闭包

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

 

分析:

 

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

 

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

 

传递闭包的定义:

 

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

 

 

#include <iostream>

#include <string.h>

#include <stdio.h>

using namespace std;

const int maxnum=101;

int map[maxnum][maxnum];

int n,m;

 

void floyd()

{

    int i,j,k;

    for(k=1;k<=n;k++)

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

                map[i][j]=map[i][j] || (map[i][k]&&map[k][j]);//判断ij是否连通

}

 

int main()

{

    scanf("%d%d",&n,&m);

    memset(map,0,sizeof(map));

    int i,j,u,v;

    for(i=0;i<m;i++)

    {

        scanf("%d%d",&u,&v);

        map[u][v]=1;

    }

    floyd();

    int ans,res=0;

    for(i=1;i<=n;i++)

    {

        ans=0;

        for(j=1;j<=n;j++)

        {

            if(i==j)    continue;

            else if(map[i][j] || map[j][i])//输入的时候当做有向图来考虑,因此需要考虑入度、出度

                ans++;

        }

        if(ans==n-1)//出度+入度=n-1

            res++;

    }

    printf("%d\n",res);

    return 0;

}