题目：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[105][105],pre[105][105],ans,path[105],inf=1e9,top; int sid[105][105];//真的有必要存直接相连的边 int main() { scanf("%d%d",&n,&m); memset(f,-1,sizeof f); memset(sid,-1,sizeof sid); ans=inf; for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if(f[x][y]==-1)// { 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=1;k<=n;k++) { for(int i=1;i<k;i++)//找环 for(int j=i+1;j<k;j++) { // if(k==5)printf("i=%d j=%d ans=%d %d ",i,j,ans,f[i][j]+sid[i][k]+sid[k][j]); if(f[i][j]!=-1&&sid[i][k]!=-1&&sid[k][j]!=-1&&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 ",k,j,sid[k][j]); // printf("ans=%d ",ans); // printf("!f[%d][%d]=%d f[%d][%d]=%d ",i,k,f[i][k],k,j,f[k][j]); top=0; int t=j; while(t!=i) { path[++top]=t; t=pre[i][t]; } path[++top]=i; path[++top]=k;//前提为k为单出一点 } } 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]>f[i][k]+f[k][j]||f[i][j]==-1))// { // printf("f[%d][%d]=%d f[%d][%d]=%d ",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=1;i<=top;i++) printf("%d ",path[i]); } return 0; }