Floyed求传递闭包 poj 3660

清疚 2022-08-25 08:29 125阅读 0赞

Floyed算法本来是求最短路的一个比较低效率的算法。

介绍[http://blog.csdn.net/y990041769/article/details/8524903][http_blog.csdn.net_y990041769_article_details_8524903]

传递闭包是什么东西呢。设R是A上的关系，我们希望R具有一些有用的性质，比如说传递性，如果R不具有传递性，我们通过在R中添加一些有序对来改造R，得到新的关系R1，使得R1具有传递性，我们有希望R1与R相差的不是太多，所以要尽可能添加少的有序对，满足这些条件的R1就是R的传递闭包。

题目：[http://poj.org/problem?id=3660][http_poj.org_problem_id_3660]

题目意思就是给出一个有向图，求能确定唯一优先级关系的点。

可以先用Floyed算法将有间接优先级关系转化为直接优先级关系的，然后判断一个点如果和所有点都有直接关系的话那么这个点的优先级关系是可以确定的。

代码：

#include <cstdio>
    #include <cstring>
    int cow[110][110];
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            if(m==0&&n==0)
                break;
            memset(cow,0,sizeof(cow));
            int x,y;
            for(int i=0;i<m;i++)
            {
                scanf("%d%d",&x,&y);
                cow[x][y]=1;
            }
            for(int k=1;k<=n;k++)  //Flolyed
                for(int i=1;i<=n;i++)
                    for(int j=1;j<=n;j++)
                        if(cow[i][k]&&cow[k][j])
                            cow[i][j]=1;
            int ans=0,i,j;
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    if(i==j)    continue;
                    if(cow[i][j]==0&&cow[j][i]==0)  break;//求
                }
                if(j>n)
                    ans++;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[http_blog.csdn.net_y990041769_article_details_8524903]: http://blog.csdn.net/y990041769/article/details/8524903
[http_poj.org_problem_id_3660]: http://poj.org/problem?id=3660