FZU 2090 无向图最小环 floyd

【题目大意】

给定一个无向图，求出图中的最小环。并输出最小环的个数。

【解题思路】

1.朴素算法。

对于边e(u,v)，除掉e之后的最短路径mind(u,v)，那么最小环则为mind(u,v)+e(u,v);

2.<图论中的圈与块>

 一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小于k的最短路径长度
    根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径
    综上所述，该算法一定能找到图中最小环。
以上文段选自（绍兴县柯桥中学 黄劲松《图论中的圈与块》）。

【CODE】

#include<iostream>
#include<cstdio>
using namespace std;struct MAP{int map[111][111];
};int main()
{int t;scanf( "%d",&t );while( t-- ){int n,m,u,v,l;scanf( "%d%d",&n,&m );MAP D,d;memset( D.map,0x0F,sizeof(D.map) );memset( d.map,0x0F,sizeof(d.map) );for( int i=0;i<m;i++ ){scanf( "%d%d%d",&u,&v,&l );if( D.map[u][v]>l )D.map[u][v]=D.map[v][u]=l;}d=D;int mind=INT_MAX;int sum=0;for( int k=1;k<=n;k++ ){for( int i=1;i<k;i++ )for( int j=i+1;j<k;j++ )if( mind>D.map[i][k]+D.map[k][j]+d.map[i][j] ){sum=1;mind=D.map[i][k]+D.map[k][j]+d.map[i][j];}else if( mind==D.map[i][k]+D.map[k][j]+d.map[i][j] )sum++;for( int i=1;i<=n;i++ )for( int j=1;j<=n;j++ )if( d.map[i][j]>d.map[i][k]+d.map[k][j] )d.map[i][j]=d.map[i][k]+d.map[k][j];}printf( "%d %d\n",mind,sum );}return 0;
}