题目大意： 给出一些双向边， 求图中的一个最小环， 当ｕ－ｖ被选中时， ｖ－ｕ不能被选， 按顺序输出这个最小环， ｎ<＝１００
无解则输出。题目既然要求最小环，数据范围还这么小， 容易联想到ＦＬＯＹＤ， 并且这里是双向边也没有什么关系， 因为只能选一条， 但题目比较麻烦的地方就是要输出这个环，
我的处理好像和机房的人不一样。。。。。
我想到的办法是对于每一个ｉ -> j的路径， 记下最优的中间点， 再记下最小环中的最大序号点， 和最小环中的ｆｌｏｙｄ的那一条路径的起点和终点， 递归输出。 开始一直ＷＡ＃２， 一开始以为是我的ＦＬＯＹＤ和网上主流的ＦＬＯＹＤ不一样， 然而好像我的ＦＬＯＹＤ那个细节地方貌似无关紧要， 然后突然发现有个BUG!!!! 因为我的最小环记下的路径是前ｋ－１个点为中间点更新后的答案， 所以一种诡异的情况就是第ｋ次恰好可以更新掉我记下的路径， 那么我输出的答案会有两个ｋ点（手动滑稽。。。。）所以我就做了两遍， 先做出最小环再跑一遍ＦＬＯＹＤ就ｏｋ好像还可以用个ｖｅｃｔｏｒ来更新答案， 不过没我的方便ｈｈｈｈ
贴代码－－－－－#include#include const int N = 100 + 10;const int oo = 1e8 + 1e7 + 7e5;#define min(a, b) a < b? a : b#define rep(i, s, t) for(int i = s; i <= t; ++i)int G[N][N], p[N], Mid, x, y, top;int n, m, a[N][N], f[N][N], Ans[N];void init() { top = 0; Mid = 0, x = 0, y = 0; rep(i, 0, n) p[i] = 0; rep(i, 0, n) rep(j, 0, n) a[i][j] = f[i][j] = oo, G[i][j] = 0;}void dfs(int i, int j) { if(a[i][j] == f[i][j]) { if(!p[i]) Ans[++top] = i, p[i] = 1; if(!p[j]) Ans[++top] = j, p[j] = 1; return ; } dfs(i, G[i][j]), dfs(G[i][j], j);}int main() {#ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("res.out", "w", stdout);#endif while(1) { scanf("%d", &n); if(n == -1) break; scanf("%d", &m); init(); rep(i, 1, m) { int u, v, w; scanf("%d%d%d", &u, &v, &w); a[u][v] = a[v][u] = min(a[u][v], w); f[u][v] = f[v][u] = a[u][v]; } rep(i, 0, n) a[i][i] = f[i][i] = 0; int Res = oo; rep(k, 1, n) { rep(i, 1, k-1) rep(j, 1, k-1) if(i ^ j) if(a[k][i] + a[j][k] + f[i][j] < Res) Res = a[k][i] + a[j][k] + f[i][j]; rep(i, 1, n) rep(j, 1, n) if(f[i][k] + f[k][j] < f[i][j]) { f[i][j] = f[i][k] + f[k][j]; G[i][j] = k; } } if(Res >= oo) { puts("No solution."); continue; } bool flag = 0; rep(i, 1, n) rep(j, 1, n) f[i][j] = a[i][j], G[i][j] = 0; rep(k, 1, n) { rep(i, 1, k-1) { rep(j, 1, k-1) if(i ^ j) if(a[k][i] + a[j][k] + f[i][j] == Res) { Mid = k, x = i, y = j; flag = 1; break; } if(flag) break; } if(flag) break; rep(i, 1, n) rep(j, 1, n) if(f[i][k] + f[k][j] < f[i][j]) { f[i][j] = f[i][k] + f[k][j]; G[i][j] = k; } } p[Mid] = 1, Ans[++top] = Mid; dfs(x, y); rep(i, 1, top) printf("%d%c", Ans[i], i^top? ' ':'\n'); } return 0;}
看起来很长吧， 其实思路很清晰的。。。。。相信你们也不会来看我的这么丑的代码