Warshall算法求传递闭包

妖狐艹你老母 2022-05-22 04:15 190阅读 0赞

![70][]

![70 1][]

![70 2][]

![70 3][]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1e3+6;
    
    int a[maxn][maxn];
    int n;
    int warshall(int a[][maxn])
    {
    	for(int i=0;i<n;i++)
    	{
    		for(int k=0;k<n;k++)
    		if(a[k][i])
    			for(int j=0;j<n;j++)
    				a[k][j]=a[k][j]|a[i][j];//逻辑加 
    	}
    	return 1;
    }
    int main()
    {
    	printf("请输入矩阵的大小n(n<=100) : ");
    	scanf("%d",&n);
    	printf("请输入矩阵：\n");
    	for(int i=0;i<n;i++)
    		for(int j=0;j<n;j++)
    			scanf("%d",&a[i][j]);
    	warshall(a);
    	printf("传递闭包是这个:\n");
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<n;j++)
    			printf("%d ",a[i][j]);
    		printf("\n");
    	}
    	return 0;
     }

[70]: /images/20220522/6ca9f71bccd84af6a588162d2b0428bb.png
[70 1]: /images/20220522/0df70217d6814b61940de1e9fba2ef17.png
[70 2]: /images/20220522/bddf8afa96ff47dd8d656276080e6e2d.png
[70 3]: /images/20220522/d40b19ca33764dc999b6a4ad989cf4b3.png

发表评论取消回复

表情：

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

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

相关阅读

相关 Warshall算法

还在为离散数学求传递闭包而迷惑？学图论还不会warshall算法？快来了解一下吧

你的名字/ 2024年04月26日 11:08/ 0 赞/ 70 阅读

相关 Floyd-Warshal算法

![0_1315389826sAEs.gif][] 先来简单分析下,由于矩阵中对角线上的元素始终为0,因此以k为中间点时,从上一个矩阵到下一个矩阵变化时,矩阵的第k行,第k

港控/mmm°/ 2024年02月18日 22:54/ 0 赞/ 66 阅读

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

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

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

相关 Floyed求传递闭包 poj 3660

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

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

相关 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 赞/ 151 阅读

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

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

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

相关 flord(传递闭包)

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

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

相关求关系的传递闭包

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

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

相关 Warshall算法求传递闭包

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

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

相关 Floyd-Warshall算法

　　Floyd也是采用动态规划的方案来解决在一个有向图G=（V，E）上每对顶点间的最短路径问题。运行时间为Θ（V3）。算法分析：　　用邻接矩阵map\[\]\[\]存储

以你之姓@/ 2021年12月17日 03:03/ 0 赞/ 329 阅读