最小环问题（无向图）

什么是最小环？就是所有组成环的环，边权值最小的环，就是最小环。

我们由一道题，进入这个问题。

链接：hdu1599

find the mincost route

Time Limit: 1000/2000 MS (Java/Others) ， Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8189 ， Accepted Submission(s): 3100

Problem Description
杭州有N个景区，景区之间有一些双向的路来连接，现在8600想找一条旅游路线，这个路线从A点出发并且最后回到A点，假设经过的路线为V1,V2,…VK,V1,那么必须满足K>2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。

Input
第一行是2个整数N和M（N <= 100, M <= 1000)，代表景区的个数和道路的条数。
接下来的M行里，每行包括3个整数a,b,c.代表a和b之间有一条通路，并且需要花费c元(c <= 100)。

Output
对于每个测试实例，如果能找到这样一条路线的话，输出花费的最小值。如果找不到的话，输出"It’s impossible.".

Sample Input
3 3
1 2 1
2 3 1
1 3 1

3 3
1 2 1
1 2 3
2 3 1

Sample Output
3
It’s impossible.

题意很简单，我们可以看出就是一个最小环寻找问题。

求最小环我们可以利用floyd来求，什么你还不会Floyd？（自己看书）

其实Floyd很简单，用四行代码就能解决。

for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			g[i][j]=g[j][i]=min(g[i][j],g[i][k]+g[k][j]);

思路也十分简单，就是利用一个点k，看i，j之间的路径能否通过k点中转，使得i，j之间的路径变短。

这里我们探讨怎么利用floyd求最小环。

我们来分析下floyd的实现过程，当枚举顶点k之前我们已经求得了顶点为1 - k-1 的最短路，所以我们可以在跟新k之前枚举k之前的i和j的组合，我们可以知道dis[i][j]没有经过k点,所以我们就可以知道，如果dis[i][j]+mp[i][k]+mp[k][j] != inf(mp[i][j]为没有跟新得边值) 时就存在一条经过ijk的最小环,所以我们要求的是所有环当
中最小的哪一个！

所以有了以下AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int inf=1e8;//这里真的超级坑，不能像以前写成0x3f3f3f3f，因为会爆int
int n,m,mp[N][N],g[N][N],res=inf;
void floyd()
{
	res=inf;
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<k;i++)
			for(int j=i+1;j<k;j++)
				res=min(res,g[i][j]+mp[i][k]+mp[k][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				g[i][j]=g[j][i]=min(g[i][j],g[i][k]+g[k][j]);
	}
}
int main()
{
	while(cin>>n>>m)
	{
		for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	if(i!=j)	mp[i][j]=g[i][j]=inf;
		while(m--)
		{
			int u,v,w;
			cin>>u>>v>>w;
			mp[u][v]=mp[v][u]=g[u][v]=g[v][u]=min(w,mp[u][v]);
		}
		floyd();
		if(res==inf)	cout<<"It's impossible."<<endl;
		else	cout<<res<<endl;
	}
	return 0;
}