poj3660 Cow Contest(Floyd-Warshall方法求有向图的传递闭包)

poj3660 Cow Contest(Floyd-Warshall方法求有向图的传递闭包)

poj3660

题意: 

有n头牛, 给你m对关系(a, b)表示牛a能打败牛b, 求在给出的这些关系下, 能确定多少牛的排名。

分析:

在这呢先说一下关系闭包:  

关系闭包有三种: 自反闭包(r), 对称闭包(s), 传递闭包(t)。

先画出 R 的关系图,再画出 r(R), s(R), t(R) 的关系图。

poj3660 Cow Contest(Floyd-Warshall方法求有向图的传递闭包)        poj3660 Cow Contest(Floyd-Warshall方法求有向图的传递闭包)       poj3660 Cow Contest(Floyd-Warshall方法求有向图的传递闭包)       poj3660 Cow Contest(Floyd-Warshall方法求有向图的传递闭包)

我们今天用的是传递闭包。   仅作为个人理解 传递闭包: 关系之间具有传递性(例如a> b, b> c, 那么a> c), 在那些已给出的关系基础上, 通过传递性, 把所有可能的关系都找出来。  如上图。

 

这里需要先求一下所有牛之间的传递闭包, 那么我们这题与传递闭包又有什么关系呢。 下面将慢慢解答。 

如果一头牛被x头牛打败,并且可以打败y头牛,如果x+y=n-1,则我们容易知道这头牛的排名就被确定了,所以我们只要将任一头牛,可以打败其他的牛的个数x, 和能打败该牛的牛的个数y求出来,在遍历所有牛判断一下是否满足x+y=n-1,就知道这个牛的排名是否能确定了(而传递闭包,正好将所有能得出关系都求出来了), 再将满足这个条件的牛数目加起来就是所求解。 x可以看成是入度, y是出度。

 

在floyd-warshall(不了解该算法的点这里)求每对顶点间的最短路径算法中,可以通过O(v^3)的方法求出图的传递闭包。可以位每条边赋以权值1,然后运行Floyd-Wareshall。如果从  i  到  j  存在一条路径,则d(i,j)<N,否则d(i,j)=MAX。

 

 一种改进的算法是:由于我们需要的只是判断是否从i到j存在一条通路,所以在Floyd-Wareshall中的动态规划比较中,我们可以把min和+操作改为逻辑or( ||  )和逻辑(&&)也就是将  d[i][j] = min(d[i][j],  d[i][k]+dist[k][j]);    改成    if(d[i][j] == 1 || (d[i][k] == 1 && d[k][j] == 1))   d[i][j] = 1;

设  d(i,j) = 1表示从 i 到 j 存在一条通路 p,且 p 的所有中间节点都在0,1,2,…,k中, 否则d(i,j)=0。我们把边(i,j)加入到E*中当且仅当d(i,j)=1。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<vector>
using namespace std;

int n, m, ans, v[110][110];

void floyd()//求图的闭包, 把所有可以确定的关系都求出来
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(v[i][j] == 1 || (v[i][k] == 1 && v[k][j] == 1))
                    v[i][j] = 1;
            }
        }
    }
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(v, 0, sizeof(v));
        for(int i = 1; i <= m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            v[x][y] = 1;
        }
        floyd();

        ans = 0;
        for(int i = 1; i <= n; i++)
        {
            int du = 0;
            for(int j = 1; j <= n; j++)//对于每头牛, 求是否有唯一排名
            {
                if(i == j) continue;
                if(v[i][j] == 1 || v[j][i] == 1)
                    du++;
            }
            if(du == n-1)
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

 

转载于:https://www.cnblogs.com/wd-one/p/4545086.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109433.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号