麻烦问下各路大牛 怎么求无向图中的最小环长度？ 万分感谢

显然该无向图存在连通分支。对每个连通分支单独进行考虑。
对于一个连通图，任取一个它的生成树（有算法可以完成这项操作），连通分支中除过这些树枝剩下的边我们称作弦，每一条弦对应该连通图的一个基本回路，无向图的所有回路都可以表示成这些基本回路的直和（边集的并，去掉公共边），所以最小回路一定在这些基本回路里产生。我们现在把这些弦一条一条往里加就可以了。加入一条弦，立即产生一个基本回路，计算此回路边数并记录在一个数组里。去掉此弦，加入另一条弦，会有另一个回路产生，计算边数，保存。把所有的弦都试一遍，得到一个数组，取最小元素对应的弦，把弦加进生成树，就得到最小回路。这样的算法很节省空间。可以得到所有最小回路。

我用的是Dijsktra算法进行的计算。假设一个环中有两个顶点A,B，那么走完这个环的最小路程是从A到B的最短路+去掉A到B的最短路上的所有路径后的A到B（B到A）的最短路（就相当于是从A走到B再走到A的最短路）

因此，在外层枚举A，算出A到各个点的最短路，同时记下路径。然后枚举每一个B，删掉A到B上最短路径所经过的边，再算一次A到B的最短路径，然后两者相加，求得一个环的最短路。最后找一个最小的环的长度，输出即可。时间复杂度到了O(n^4)，所以我有一组花了0.9s.

但是这道题的难点在于那个BT的INPUT-------从来都没有见过的图的输入方式：告诉的是边与边的关系。

我是这样解决的：找出所有的边的两个端点（不管是否重复），并把这些端点连了哪些边记录下来。然后去掉重复的顶点，剩下的就是图的顶点。接着通过枚举寻找任意两个顶点是否都连了相同的边，如果连了，说明这两个顶点就是被这条边所连，因此就可以在邻接矩阵中记录下来。时间复杂度O(n^3)

这一题是我一次AC的。。。难得在USACO Cheapter4 里面一次AC哈。。

Cherry还有更好的O(n^3)的算法，我也不知道怎么做的。感兴趣的去看一下子。

这是你们竞赛的题目吧？我回答了就不公平了。