https://vjudge.net/problem/14074
给定一个有n个点的无向图，有m条无向边，求图中一个至少包含三个点的环，并输出环上的点，有多解任意输出一个即可，没有这样的环则输出No solution.
可以用floyd算法求解最小环，然后记录路径输出即可。 关于记录路径：定义pro[i][j]为点i到点j路径上的倒数第二个点，倒数第一个自然是j，初始化pro[i][j]为i。当dis[i][j] > dis[i][k] + dis[k][j]成立时，意味着点i到点j的路径要改成点i到点k再到点j，而dis[k][j]已知，意味着pro[k][j]已知，即点k到点j的路径已知，所以此时应该把pro[k][j]存到pro[i][j]中，即pro[i][j] = pro[k][j]
#include <bits/stdc++.h> using namespace std; const int N = 110, INF = 1<<28; int n, m, tot; int g[N][N], dis[N][N], pro[N][N], path[N]; int floyd() { int res = INF; for(int k = 1; k <= n; k++) { for(int i = 1; i < k; i++) for(int j = i+1; j < k; j++) { int tmp = dis[i][j] + g[i][k] + g[k][j]; if(res > tmp) { res = tmp; tot = 0; int p = j; while(p != i) { path[tot++] = p; p = pro[i][p]; } path[tot++] = i, path[tot++] = k; } } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(dis[i][j] > dis[i][k] + dis[k][j]) { dis[i][j] = dis[i][k] + dis[k][j]; pro[i][j] = pro[k][j]; } } return res; } int main() { while(scanf("%d", &n), n != -1) { scanf("%d", &m); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { if(i == j) g[i][j] = dis[i][j] = 0; else g[i][j] = dis[i][j] = INF; pro[i][j] = i; } for(int i = 1; i <= m; i++) { int v, u, c; scanf("%d%d%d", &v, &u, &c); g[v][u] = g[u][v] = dis[v][u] = dis[u][v] = min(g[v][u], c); } int res = floyd(); if(res == INF) printf("No solution.\n"); else { for(int i = tot-1; i >= 0; i--) printf("%d%c", path[i], i == 0 ? '\n' : ' '); } } return 0; }