POJ - 3660 Cow Contest(最短路变形+闭包传递)

65 阅读 0 评论 43 点赞

我是靠谱客的博主搞怪面包，最近开发中收集的这篇文章主要介绍POJ - 3660 Cow Contest(最短路变形+闭包传递)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：点击查看

题目大意：给定n头牛和m个关系，每个关系表示为两个整数a与b，其意义为a牛能打败b牛，问可以确定排名的牛的数量。

题目分析：

在这里先说一下关系闭包：

关系闭包有三种：自反闭包（r），对称闭包（s），传递闭包（t）。

先画出 R 的关系图，再画出 r（R），s（R）， t（R）的关系图。

这个题用到的是关系闭包。

复制一段别人的理解：

关系之间具有传递性（例如a> b, b> c, 那么a> c），在那些已给出的关系基础上，通过传递性，把所有可能的关系都找出来。

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

如果一头牛被x头牛打败，并且可以打败y头牛，如果x+y=n-1，则我们容易知道这头牛的排名就被确定了，所以我们只要将任一

头牛，可以打败其他的牛的个数x，和能打败该牛的牛的个数y求出来，在遍历所有牛判断一下是否满足x+y=n-1，就知道这个牛

的排名是否能确定了（而传递闭包，正好将所有能得出关系都求出来了），再将满足这个条件的牛数目加起来就是所求解。 x可

以看成是入度， y是出度。

在floyd-warshall求每对顶点间的最短路径算法中，可以通过O( ${n}^3$ )的方法求出图的传递闭包。可以位每条边赋以权值1，然后运行

Floyd-Wareshall。如果从 i 到 j 存在一条路径，则d(i,j)<N,否则d(i,j)=MAX。

在这里有两个细节可以优化一下Floyd：

使用位运算代替加号
适当进行剪枝

直接上代码了，更详细的请看注释：

#include<iostream>
#include<cstdio> 
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<cmath>
using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const int N=110;

int n,m;

int maze[N][N];

void floyd()//求图的闭包，可以把所有的关系求出来 
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
		{
			if(!maze[i][k])//剪枝，如果maze[i][j]为0，则maze[i][k]&maze[k][j]必为0，
//对于原结果来说没有影响，故没有继续下一层循环的必要
				continue;
			for(int j=1;j<=n;j++)
			{
				maze[i][j]|=maze[i][k]&maze[k][j];
			}
		}
}

int main()
{
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(maze,0,sizeof(maze));//因为是求闭包关系，所以全部初始化为0 
		for(int i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			maze[a][b]=1;//有关系的设置为1，利用位运算能加快速度 
		}
		floyd();
		int ans=0;
		for(int i=1;i<=n;i++)//外层遍历一边n个点
		{
			int cnt=0;
			for(int j=1;j<=n;j++)//内层遍历一边除了i点外的n-1个点
			{
				if(i==j)
					continue;
				if(maze[i][j]||maze[j][i])//maze[i][j]==1表示i能打败j，maze[j][i]==1表示j能打败i
					cnt++;
			}
			if(cnt==n-1)//如果i点与其余n-1个点都有关系，则i点的关系是可以被确定的
				ans++;
		}
		cout<<ans<<endl;
	}
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}