poj1734Sightseeing trip——无向图求最小环

题目：http://poj.org/problem?id=1734

无向图求最小环，用floyd；

在每个k点更新f[i][j]之前，以k点作为直接连到i,j组成一个环的点，这样找一下最小环；

注意必须存直接相连的边，在找环时k点连到i,j的值不能是最短路。

调了一个小时发现把z打成y了......

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,f[][],pre[][],ans,path[],inf=1e9,top;

int sid[][];//真的有必要存直接相连的边

int main()

{

    scanf("%d%d",&n,&m);

    memset(f,-,sizeof f);

    memset(sid,-,sizeof sid);

    ans=inf;

    for(int i=;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        if(f[x][y]==-)//

        {

            f[x][y]=f[y][x]=z;

            pre[x][y]=x;pre[y][x]=y;

            sid[x][y]=z;sid[y][x]=z;

        }

        else

            f[x][y]=f[y][x]=sid[x][y]=sid[y][x]=min(f[x][y],z);

    }

    for(int k=;k<=n;k++)

    {

        for(int i=;i<k;i++)//找环

            for(int j=i+;j<k;j++)

            {

//                if(k==5)printf("i=%d j=%d  ans=%d %d\n",i,j,ans,f[i][j]+sid[i][k]+sid[k][j]);

                if(f[i][j]!=-&&sid[i][k]!=-&&sid[k][j]!=-&&ans>f[i][j]+sid[i][k]+sid[k][j])

                {

                    ans=f[i][j]+sid[i][k]+sid[k][j];

//                    printf("sid[%d][%d]=%d\n",k,j,sid[k][j]);

//                    printf("ans=%d\n",ans);

//                    printf("!f[%d][%d]=%d f[%d][%d]=%d\n",i,k,f[i][k],k,j,f[k][j]);

                    top=;

                    int t=j;

                    while(t!=i)

                    {

                        path[++top]=t;

                        t=pre[i][t];

                    }

                    path[++top]=i;

                    path[++top]=k;//前提为k为单出一点

                }

            }

        for(int i=;i<=n;i++)//

            for(int j=;j<=n;j++)//

                if(f[i][k]!=-&&f[k][j]!=-&&(f[i][j]>f[i][k]+f[k][j]||f[i][j]==-))//

                {

//                    printf("f[%d][%d]=%d f[%d][%d]=%d\n",i,k,f[i][k],k,j,f[k][j]);

                    f[i][j]=f[i][k]+f[k][j];

                    pre[i][j]=pre[k][j];

                }

    }

    if(ans==inf)printf("No solution.");

    else

    {

        for(int i=;i<=top;i++)

            printf("%d ",path[i]);

    }

    return ;

}