poj3660 cow contest

这题主要是传递闭包

题意： n头牛，m次测试，假设a牛赢过b牛，那么说明a牛的能力比b牛强，问你根据输入的m次测试结果，最多能确定多少条牛的排名

大题的思路：

　　对于 k 牛，比他强的有x头牛，比他弱的有y头牛，只要x+y == n-1，那么x的排名就能确定

　　也就是求任意两头牛之间能否到达

　　每次测试都能加入一条新的边，用floyd求任意两点间能否抵达

　　最后根据比他强和比他弱的个数求和等于n-1说明这头牛能确定排名

　　。。。。。。

有点小细节：这个题假设a牛能胜过b牛，代表的是能力值高低，我们也是只要求确定能力值的排名，所以a牛赢过b牛，b牛赢过c牛，那么a牛一定能赢过c牛，c牛不可能赢过a牛

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

int dis[][];

void flo(int n);

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m) != EOF)

    {

        memset(dis,,sizeof(dis));

        while(m--)

        {

            int a,b;

            scanf("%d %d",&a,&b);

            dis[a][b] = ;

        }

        flo(n);

        int ans = ;

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

        {

            int c = ;

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

            {

                if(dis[i][j] ==  || dis[j][i]) c ++;

            }

            if(c == n-) ans ++;

        }

        cout << ans << endl;

    }

}

void flo(int n)

{

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

    {

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

        {

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

            {
　　　　　　　　　　//dis[i][i] 一定等于0   不用i==j continue

                if(dis[i][k] ==  && dis[k][j] == )

                    dis[i][j] = ;

            }

        }

    }

}

巴特西

poj3660 cow contest

最新文章

热门文章