【URAL 1004】 floyd最小环

题目链接：http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=14074

题目大意：给你一个n个点加权无向图，要你从里面找一个路径最短的环，每个点只能经过一次，如果存在这样的最短环则把路径给打印出来，如果有多个，打印一个出来即可。

解题思路：

最小环的定义：经过一条简单路径（除起点每点只经过一次）回到起点成为环，并且环的总长度最小称为最小环。

开始直接用floyd求每个点的dist[X][X]，发现输出的时候问题很大，本题是floyd的扩展板。

如果简单的floyd打印路径算法还不熟悉可以看看这个博客的解释，很详细。http://blog.sina.com.cn/s/blog_6fbae1120100xfdd.html

回到重点，如果用简单的floyd求最小环，你会发现在求最短路的过程中有很多点是重复经过的。现在的问题是怎么找没有重复经过同一个点的最小环，这个问题才是整个floyd扩展板的关键。

举个例子，不重复经过同一个点的最小环可以这么表示：u-->（x1-->x2-->x3-->……-->xm）-->v-->k-->u （其中u和k，v和k是直接相连的，（x1-->x2-->x3-->……-->xm）指的是不经过k的点u到v的最短路径）。在u，v，k确定的情况下，要是总环最小，说明只需要（x1-->x2-->x3-->……-->xm）和最小，即让u到v的最短路径最小，这个最短路径可以用floyd三循环完成。只差一步，现在的问题是让（x1-->x2-->x3-->……-->xm）与k不重复。所以在这里我们对k做一个限制，即让k节点比u，v，x，都大，而u和k，k和v都是直接相连的，对k进行一次遍历（1->n）,接着镶嵌两个for循环 i（1->k-1） j（i+1->k-1），这样就保证了u，v，（x1-->x2-->x3-->……-->xm）一定比k小了，当然也就不会重复经过k了。

我们可以发现，Floyd和最后枚举u，v,k三个变量求最小环的过程都是u,v,k三个变量，所以我们可以将其合并。这样，我们在k变量变化的同时，也就是进行Floyd算法的同时，寻找最大点为k的最小环。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn=110;
const int INF=0x7ffffff;
int  dist[maxn][maxn], map[maxn][maxn];
int  pre[maxn][maxn];
int  path[maxn];
int  n, m, num, minc;

void floyd()
{
    minc=INF;
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<k; i++)
            for(int j=i+1; j<k; j++)
            {
                int  ans=dist[i][j]+map[i][k]+map[k][j];
                if(ans<minc)  //找到最优解
                {
                    minc=ans;
                    num=0;
                    int p=j;
                    while(p!=i)  //逆向寻找前驱遍历的路径并将其存储起来
                    {
                        path[num++]=p;
                        p=pre[i][p];
                    }
                    path[num++]=i;
                    path[num++]=k;
                }
            }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                if(dist[i][j]>dist[i][k]+dist[k][j])
                {
                    dist[i][j]=dist[i][k]+dist[k][j];
                    pre[i][j]=pre[k][j];
                }
            }
    }
}

int main()
{
    int  u, v, cost;
    while(cin >> n)
    {
        if(n<0) break;
        cin >> m;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                dist[i][j]=map[i][j]=INF;
                pre[i][j]=i;
            }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&u,&v,&cost);
            if(dist[u][v]>cost)   //处理重边
                map[u][v]=map[v][u]=dist[u][v]=dist[v][u]=cost;
        }
        floyd();
        if(minc==INF)
            printf("No solution.\n");
        else
        {
            printf("%d",path[0]);
            for(int i=1; i<num; i++)
                printf(" %d",path[i]);
            puts("");
        }
    }
    return 0;
}