求简单加权有向图的最大环的C++代码

求简单加权有向图的最大环可以使用 Floyd 算法。具体步骤如下：

1. 定义一个二维数组 dist，表示任意两点之间的最短路径长度。初始化为图中边的权重，如果两点之间没有边，则距离为无穷大。

2. 定义一个二维数组 path，表示任意两点之间的最短路径上，从起点到终点的前一个节点。初始化为起点到终点的直接前驱。

3. 使用 Floyd 算法，更新 dist 和 path 数组。具体更新方法如下：

for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] > dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[k][j];
}
}
}
}

4. 遍历 dist 数组，找到任意一条长度大于0且形成环的路径。具体代码如下：

int max_cycle = 0;
for (int i = 0; i < n; i++) {
if (dist[i][i] > 0 && dist[i][i] != INF) {
int j = i;
int cycle = 0;
do {
j = path[i][j];
cycle += dist[j][i];
} while (j != i);
max_cycle = max(max_cycle, cycle);
}
}

完整的 C++ 代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

int n;
int dist[MAXN][MAXN];
int path[MAXN][MAXN];

int main() {
    cin >> n;
    // 初始化 dist 和 path 数组
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
            if (i != j && dist[i][j] == 0) {
                // 如果两点之间没有边，则距离为无穷大
                dist[i][j] = INF;
            }
            path[i][j] = j;
        }
    }
    // Floyd 算法更新 dist 和 path 数组
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] > dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j];
                }
            }
        }
    }
    // 找到最大环的长度
    int max_cycle = 0;
    for (int i = 0; i < n; i++) {
        if (dist[i][i] > 0 && dist[i][i] != INF) {
            int j = i;
            int cycle = 0;
            do {
                j = path[i][j];
                cycle += dist[j][i];
            } while (j != i);
            max_cycle = max(max_cycle, cycle);
        }
    }
    cout << "最大环的长度为：" << max_cycle << endl;
    return 0;
}