题意：给定一个N个点的无向图，求其中的最小的环。输出路径。
其实这个板子我还有不理解的地方。输出路径的方法值得学习。
#include#include #include #define MAX 100+10#define INF 0x3f3f3f3fusing namespace std;int n, m;int map[MAX][MAX];int dis[MAX][MAX];int pre[MAX][MAX];int res[MAX];int tmp;void Getpath(int i, int j, int k) { tmp = 0; while (j != i) { res[tmp++] = j; j = pre[i][j]; } res[tmp++] = i; res[tmp++] = k;}void Floyd() { int ans = INF; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) dis[i][j] = map[i][j]; } for (int k = 1; k <= n; k++) { for (int i = 1; i < k; i++) {//为什么要小于k for (int j = i + 1; j < k; j++) {//为什么要小于k if (map[k][j] < INF && map[k][i] < INF && dis[i][j] map[k][i] + map[k][j] + dis[i][j]) { ans = dis[i][j] + map[k][j] + map[k][i]; Getpath(i, j, k); } } } for (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][k] < INF && dis[j][k] < INF) { dis[i][j] = dis[i][k] + dis[k][j]; pre[i][j] = pre[k][j]; pre[j][i] = pre[k][i]; } } } } if (ans == INF) { printf("No solution.\n"); } else { for (int i = 0; i < tmp; i++) printf("%d%c", res[i], i == tmp - 1 ? '\n' : ' '); }}int main(void) { while (~scanf("%d%d", &n, &m)) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) if (i == j) map[i][j] = 0; else map[i][j] = INF; } for (int i = 1; i <= m; i++) { int a, b, d; scanf("%d%d%d", &a, &b, &d); if (map[a][b] > d) { map[a][b] = d; map[b][a] = d; pre[a][b] = a; pre[b][a] = b; } } Floyd(); } system("pause"); return 0;}