• 题目大意

  求一个无向图的最小环

• 题解

  假设是有向图的话。仅仅须要令f[i][i]=+∞，再floyd就可以；
  对无向图。应该在floyd算法循环至k的一開始进行例如以下操作：
  枚举i和j，假设点i存在经过点j的环，则用i→k。k→j，j→编号小于k的结点→i 的最短路去更新最小环的长度，
  即ans=min{
  ans,map[i][k]+map[k][j]+f[i][j]}
  然后更新最小环。
  这个工作进行完之后。才干够用floyd计算i→k→j的最短路。

• Code

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int oo = 1000000000;int n, m, map[110][110], pre[110][110], f[110][110];int ans, path[110], top;void init(){    int x, y, z;    scanf("%d%d", &n, &m);    memset(f, -1, sizeof(f));    memset(map, -1, sizeof(map));    memset(pre, -1, sizeof(pre));    for(int i = 1; i <= m; ++i)    {        scanf("%d%d%d", &x, &y, &z);        if(f[x][y] == -1)        {            f[x][y] = f[y][x] = map[x][y] = map[y][x] = z;        }        else        {            f[x][y] = f[y][x] = map[x][y] = map[y][x] = min(map[x][y], z);        }        pre[x][y] = x;        pre[y][x] = y;    }    for(int i = 1; i <= n; ++i)    {        f[i][i] = map[i][i] = 0;    }    ans = oo;}void work(){    for(int k = 1; k <= n; ++k)    {        for(int i = 1; i < k; ++i)        {            for(int j = i + 1; j < k; ++j)            {                if(map[i][k] != -1 && map[k][j] != -1 && f[i][j] != -1 && ans > f[i][j] + map[i][k] + map[k][j])                {                    ans = f[i][j] + map[i][k] + map[k][j];                    int t = j;                    top = 0;                    while(t != i)                    {                        path[++top] = t;                        t = pre[i][t];                    }                    path[++top] = i;                    path[++top] = k;                }            }        }        //以上为找最小环        //下面为floyd更新最短路        for(int i = 1; i <= n; ++i)        {            for(int j = 1; j <= n; ++j)            {                if(f[i][k] != -1 && f[k][j] != -1 && (f[i][j] == -1 || f[i][j] > f[i][k] + f[k][j]))                {                    f[i][j] = f[i][k] + f[k][j];                    pre[i][j] = pre[k][j];                }            }        }    }    if(ans == oo)    {        puts("No solution.");        return;    }    for(int i = 1; i <= top; ++i) printf("%d ", path[i]);}int main(){    init();    work();    return 0;}