Floyd算法的高级应用
牛的旅行：求连通块连接后的最大直径
给定一组点和边，计算两个连通块连接后可能的最大直径。需要考虑两种情况：
- 连接前的直径。
- 连接后的直径。
以下是解决问题的步骤：
- 根据输入构建图。
- 使用Floyd算法计算所有点对之间的最短路径。
- 通过比较找到最大直径。
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int MAX_N = 155;
const double INF = 1e20;
struct Point {
double x, y;
};
int n;
Point points[MAX_N];
double dists[MAX_N][MAX_N], max_dist_per_point[MAX_N];
double calc_distance(Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void floyd() {
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dists[i][k] + dists[k][j] < dists[i][j]) {
dists[i][j] = dists[i][k] + dists[k][j];
}
}
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> points[i].x >> points[i].y;
}
memset(dists, 0x3f, sizeof(dists));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) dists[i][j] = 0;
else dists[i][j] = calc_distance(points[i], points[j]);
}
}
floyd();
double max_diameter = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dists[i][j] < INF / 2) {
max_dist_per_point[i] = max(max_dist_per_point[i], dists[i][j]);
}
}
max_diameter = max(max_diameter, max_dist_per_point[i]);
}
cout << fixed << setprecision(6) << max_diameter << endl;
return 0;
}
传递闭包与拓扑排序
利用Floyd算法求解传递闭包，并结合拓扑排序判断是否存在矛盾或唯一顺序。
- 如果存在环，则无法确定顺序。
- 如果拓扑序不唯一，则无法完全确定所有点的顺序。
- 否则输出唯一的拓扑序列。
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 26;
bool graph[MAX_N][MAX_N];
bool visited[MAX_N];
void update_graph() {
for (int k = 0; k < MAX_N; ++k) {
for (int i = 0; i < MAX_N; ++i) {
for (int j = 0; j < MAX_N; ++j) {
graph[i][j] |= graph[i][k] && graph[k][j];
}
}
}
}
char find_min_unvisited() {
for (int i = 0; i < MAX_N; ++i) {
if (!visited[i]) {
bool is_min = true;
for (int j = 0; j < MAX_N; ++j) {
if (!visited[j] && graph[j][i]) {
is_min = false;
break;
}
}
if (is_min) {
visited[i] = true;
return 'A' + i;
}
}
}
return '\0';
}
int main() {
int n, m;
while (cin >> n >> m && (n || m)) {
memset(graph, 0, sizeof(graph));
for (int i = 0; i < m; ++i) {
char s[5];
cin >> s;
int a = s[0] - 'A', b = s[2] - 'A';
graph[a][b] = true;
update_graph();
}
// Check for cycles or ambiguity
bool has_cycle = false, ambiguous = false;
for (int i = 0; i < MAX_N; ++i) {
if (graph[i][i]) {
has_cycle = true;
break;
}
}
if (!has_cycle) {
for (int i = 0; i < MAX_N; ++i) {
for (int j = i + 1; j < MAX_N; ++j) {
if (!graph[i][j] && !graph[j][i]) {
ambiguous = true;
break;
}
}
}
}
if (has_cycle) {
cout << "Inconsistency found." << endl;
} else if (ambiguous) {
cout << "Cannot determine sorted sequence." << endl;
} else {
memset(visited, 0, sizeof(visited));
string result = "";
for (int i = 0; i < n; ++i) {
result += find_min_unvisited();
}
cout << "Sorted sequence: " << result << endl;
}
}
return 0;
}
最小环问题
使用Floyd算法寻找图中的最小环。
关键思路是假设当前环中编号最大的节点为k，然后枚举与其相连的两个节点i和j，计算环的长度并更新最小值。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 110, INF = 0x3f3f3f3f;
int n, m;
int distances[MAX_N][MAX_N], original_graph[MAX_N][MAX_N];
int path_nodes[MAX_N][MAX_N], min_cycle_path[MAX_N], cycle_count;
void reconstruct_path(int i, int j) {
if (path_nodes[i][j] == 0) return;
int k = path_nodes[i][j];
reconstruct_path(i, k);
min_cycle_path[cycle_count++] = k;
reconstruct_path(k, j);
}
int main() {
cin >> n >> m;
memset(original_graph, 0x3f, sizeof(original_graph));
for (int i = 1; i <= n; ++i) original_graph[i][i] = 0;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
original_graph[u][v] = original_graph[v][u] = min(original_graph[u][v], w);
}
memcpy(distances, original_graph, sizeof(original_graph));
int min_cycle_length = INF;
for (int k = 1; k <= n; ++k) {
for (int i = 1; i < k; ++i) {
for (int j = i + 1; j < k; ++j) {
if ((long long)distances[i][j] + original_graph[i][k] + original_graph[k][j] < min_cycle_length) {
min_cycle_length = distances[i][j] + original_graph[i][k] + original_graph[k][j];
cycle_count = 0;
min_cycle_path[cycle_count++] = k;
min_cycle_path[cycle_count++] = i;
reconstruct_path(i, j);
min_cycle_path[cycle_count++] = j;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (distances[i][j] > distances[i][k] + distances[k][j]) {
distances[i][j] = distances[i][k] + distances[k][j];
path_nodes[i][j] = k;
}
}
}
}
if (min_cycle_length == INF) {
cout << "No solution." << endl;
} else {
for (int i = 0; i < cycle_count; ++i) {
cout << min_cycle_path[i] << " ";
}
cout << endl;
}
return 0;
}
恰好经过K条边的最短路径
结合矩阵快速幂和Floyd思想解决此问题。
- 离散化处理点编号。
- 通过快速幂优化计算过程。
#include <iostream>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
const int MAX_N = 1010;
int K, total_nodes, edges, start_node, end_node;
map<int, int> node_id;
int graph[MAX_N][MAX_N], result_graph[MAX_N][MAX_N];
void matrix_multiply(int res[][MAX_N], int a[][MAX_N], int b[][MAX_N]) {
static int temp[MAX_N][MAX_N];
memset(temp, 0x3f, sizeof(temp));
for (int i = 1; i <= total_nodes; ++i) {
for (int j = 1; j <= total_nodes; ++j) {
for (int k = 1; k <= total_nodes; ++k) {
temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
}
}
}
memcpy(res, temp, sizeof(temp));
}
void fast_power() {
while (K) {
if (K & 1) matrix_multiply(result_graph, result_graph, graph);
matrix_multiply(graph, graph, graph);
K >>= 1;
}
}
int main() {
cin >> K >> edges >> start_node >> end_node;
memset(graph, 0x3f, sizeof(graph));
node_id[start_node] = ++total_nodes;
node_id[end_node] = ++total_nodes;
start_node = node_id[start_node];
end_node = node_id[end_node];
for (int i = 0; i < edges; ++i) {
int weight, u, v;
cin >> weight >> u >> v;
if (!node_id.count(u)) node_id[u] = ++total_nodes;
if (!node_id.count(v)) node_id[v] = ++total_nodes;
u = node_id[u];
v = node_id[v];
graph[u][v] = graph[v][u] = min(graph[u][v], weight);
}
memset(result_graph, 0x3f, sizeof(result_graph));
for (int i = 1; i <= total_nodes; ++i) result_graph[i][i] = 0;
fast_power();
cout << result_graph[start_node][end_node] << endl;
return 0;
}
