传递闭包优化

本文主要是介绍传递闭包优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：传递闭包也是我们图论会遇到的，我们一般情况下会用弗洛伊德算法，但是复杂度太高了，$n^3$ 在一些题目中是会爆炸的，我们怎么去优化呢

---

没有优化的版本

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;const int N = 101;
int a[N][N];
int n;int main(){cin >> n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin >> a[i][j];}}	for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){//if(a[i][j]) break;if(a[i][k] && a[k][j]){a[i][j] = 1; //break;}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout << a[i][j] << " ";}cout << endl;}	return 0;
}

这篇关于传递闭包优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---