flord(传递闭包)

我就是我 2022-07-13 15:28 161阅读 0赞

**传递指对于一个节点i，如果j能到i，i能到k，那么j就能到k。**

**传递闭包，就是把图中所有满足这样传递性的节点都弄出来，计算完成后，我们也就知道任意两个节点之间是否相连。**

**break 指跳出一层循环；continue 结束本次循环，跳过本次判断语句**

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

**每只奶牛的技能独一无二，如果给奶牛们排序的话，能确定自己技能水平的奶牛排序后位置不变。**

**一只奶牛可以确定自己的水平，则一定和其他n-1只奶牛直接或间接比试过。**

**使用Floyd传递闭包算法，统计能赢过它的奶牛数+它赢过的奶牛数。如果这个数字等于n-1，说明该奶牛的水平可以确定。**

#include <iostream>
    using namespace std;
    const int max_n=101;
    bool dp[max_n][max_n];
    int main()
    {
    	int n,m;
    	cin>>n>>m;
    	for(int i=1;i<=m;i++)
    	{
    		int a,b;
    		cin>>a>>b;
    		dp[a][b]=true;
    	}
    	for(int k=1;k<=n;k++)
    		for(int i=1;i<=n;i++)
    			for(int j=1;j<=n;j++)
    			{
    				if(i==k||i==j||j==i)
    					continue;
    				dp[i][j]=dp[i][j]||(dp[i][k]&&dp[k][j]);
    			}
    	int ans=0;
    	for(int i=1;i<=n;i++)
    	{
    		int sum=0;
    		for(int j=1;j<=n;j++)
    		{
    			if(i!=j&&dp[i][j]) sum++;
    		}
    		for(int j=1;j<=n;j++)
    		{
    			if(i!=j&&dp[j][i]) sum++;
    		}
    		if(sum==n-1) ans++;
    	}
    	cout<<ans;
    	return 0;
    }

**flord算法要K先循环。**

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

发表评论取消回复

表情：

评论列表（有 0 条评论，161人围观）

还没有评论，来说两句吧...

相关阅读

相关 H - Cow Contest POJ - 3660——————floyd（传递闭包）

[H - Cow Contest POJ - 3660][] include<cstdio> include<cstring> include<ios

爱被打了一巴掌/ 2023年05月29日 03:12/ 0 赞/ 17 阅读

相关 343 排序（floyd算法求解传递闭包）

1. 问题描述：给定 n 个变量和 m 个不等式。其中 n 小于等于 26，变量分别用前 n 的大写英文字母表示。不等式之间具有传递性，即若 A > B 且 B > C，则

刺骨的言语ヽ痛彻心扉/ 2022年09月17日 03:01/ 0 赞/ 152 阅读

相关 Floyed求传递闭包 poj 3660

Floyed算法本来是求最短路的一个比较低效率的算法。介绍[http://blog.csdn.net/y990041769/article/details/8524903]

清疚/ 2022年08月25日 08:29/ 0 赞/ 161 阅读

相关 POJ 3660 Cow Contest（传递闭包floyed算法）

Description N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a pr

╰+哭是因爲堅強的太久メ/ 2022年08月09日 13:46/ 0 赞/ 148 阅读

相关 javascript技巧:用闭包传递参数

<html> <script> function aaa(s){ return function(){

雨点打透心脏的1/2处/ 2022年08月07日 03:43/ 0 赞/ 235 阅读

相关 flord(传递闭包)

传递指对于一个节点i，如果j能到i，i能到k，那么j就能到k。传递闭包，就是把图中所有满足这样传递性的节点都弄出来，计算完成后，我们也就知道任意两个节点之间是否相连。 b

我就是我/ 2022年07月13日 15:28/ 0 赞/ 162 阅读

相关闭包

1、定义：当一个内部函数被其外部函数之外的变量引用时，就形成了一个闭包 function A(){ var count = 0;

素颜马尾好姑娘i/ 2022年06月09日 09:20/ 0 赞/ 238 阅读

相关闭包

先来看一个题目例子，我将在下一环节出闭包讲解。。题目描述实现函数 makeClosures，调用之后满足如下条件： 1、返回一个函数数组 result，长度与

喜欢ヅ旅行/ 2022年06月04日 05:51/ 0 赞/ 233 阅读

相关求关系的传递闭包

<table style="width:1615px; margin-bottom:20px; background-color:transparent"> <tbody>

川长思鸟来/ 2022年06月02日 08:58/ 0 赞/ 177 阅读

相关 Warshall算法求传递闭包

![70][] ![70 1][] ![70 2][] ![70 3][] include<cstdi

妖狐艹你老母/ 2022年05月22日 04:15/ 0 赞/ 189 阅读