ProApe

算法

OJ题(25) 数据结构(7)

/ 注册

全部文章 / 算法（共4篇）

Warshall算法求有向图的传递闭包

1定义是这样给出的，传递闭包：对于任何关系 R，R 的传递闭包总是存在的。传递关系的任何家族的交集也是传递的。进一步的，至少存在一个包含 R 的传递关系，也就是平凡的: X × X。R 传递闭包给出自包含 R 的所有传递关系的交集……其实就是求点与点之间的可达关系，比如1–>4,4–>6...

2020-01-02

0 1666

Floyd算法计算最短路并记录路径

1计算最短路有弗洛伊德和迪杰斯塔拉两种算法，前可以计算出任意两个顶点之间的最短路径，后用于计算特定两个顶点之间的最短路径，Floyd算法用于计算无向或者有向图加权图（不包括长度为负的回路）的完全最短路径 2Floyd算法的构造过程和Warshall算法非常相似，通过初试的权重矩阵，每次加入一个顶点...

2020-01-02

1 1998

有向图求最小环

1 先用拓扑排序将多余的顶点去除，只剩下组成环的点，然后用DFS求出每个环的长度 #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define pi acos(-1.0) #define e...

2020-01-02

0 785

HDU Cotree(换根dp,树的重心)

我是看了这位大佬的博客，感谢大佬他的博客题目描述：有两颗树，需要在这两棵树之间添加一条边，这样就变成了一棵树，求这棵树任意两点之间的最小距离和即$$\sum ^{N}{i=1}\sum ^{N}{j=i+1}dis\left( i,j\right)$$ 解题思路：首先考虑，我们要在哪两个点...

2020-01-02

0 768