本文主要是介绍poj 1734 （floyd求最小环并打印路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
求图中的一个最小环，并打印路径。
解析：
ans 保存最小环长度。
一直wa，最后终于找到原因，inf开太大爆掉了。。。
虽然0x3f3f3f3f用memset好用，但是还是有局限性。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 100 + 10;
const int inf = 9999999; //0x3f3f3f3f;int g[maxn][maxn], dis[maxn][maxn];
int road[maxn][maxn], path[maxn];
int n, m, index, ans;void record(int s, int t)
{if (road[s][t]){record(s, road[s][t]);record(road[s][t], t);}else{path[index++] = t;}
}void floyd()
{ans = inf;for (int k = 1; k <= n; k++){///最小环for (int i = 1; i < k; i++){for (int j = i + 1; j < k; j++){if (dis[i][j] + g[i][k] + g[k][j] < ans){ans = dis[i][j] + g[i][k] + g[k][j];index = 0;path[index++] = i;record(i, j);path[index++] = k;}}}///floydfor (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (dis[i][k] + dis[k][j] < dis[i][j]){dis[i][j] = dis[i][k] + dis[k][j];road[i][j] = k;}}}}
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALwhile (~scanf("%d%d", &n, &m)){// memset(dis, inf, sizeof(dis));for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){dis[i][j] = inf;}}memset(road, 0, sizeof(road));for (int i = 0; i < m; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);if (w < dis[u][v]){dis[u][v] = w;dis[v][u] = w;}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){g[i][j] = dis[i][j];}}floyd();if (ans == inf){printf("No solution.\n");}else{for (int i = 0; i < index - 1; i++){printf("%d ", path[i]);}printf("%d\n", path[index - 1]);}}return 0;
}
这篇关于poj 1734 （floyd求最小环并打印路径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
