标签：图结构
最短路
题目大意：给你一个无向图，至少经过3个节点的简单回路（不能包括其他环）
一开始的思路：用一个NUM[i][j]表示i到j的最短路经过几个节点,显然解法不太优美，而且还是错的
再想了的思路：当存在一个中间点来更新F[i][j]的时候顺便更新ans，这样求出来的不是一个简单回路....会经过重复节点
此时我终于知道 我题目意思都没思考清楚...题目的意思是。。
保证环不能有交点...
题解：
将环劈成三段..
环，，i,j,k三点，环长则为三点 两两间距，
且路不能有交点，
所以，我们想到map[i][j] + dist[i][k] + dist[j][k]
map记录最短路，dist记录直接相连的边
只要map[i][j]不过k点就算得出一个环
让最短路不过k点
想到floyd的dp方程
结果呼之欲出了吧~~我就不说了，直接上伪代码
g[i][j]=(i,j之间的边长)
dist:=g;
for k:=1 to n do
begin
for i:=1 to k-1 do
for j:=i+1 to k-1 do
answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
for i:=1 to n do
for j:=1 to n do
dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
end;
关于算法<2>的证明：
一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小于k的最短路径长度
根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径
综上所述，该算法一定能找到图中最小环。
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define INF 10000000
#define MAX 101
int n,m,map[MAX][MAX];
int floyd()
{
int mincircle = INF;
int Dist[n+1][n+1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
Dist[i][j] = map[i][j];
}
for(int k = 1; k <= n; k++)
{
for(int i = 1; i < k; i++)
for(int j = i+1; j < k; j++)
{
mincircle = min(mincircle,Dist[i][j]+map[j][k]+map[k][i]);
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
Dist[i][j] = min(Dist[i][j],Dist[i][k] + Dist[k][j]);
}
}
return mincircle;
}
void init()
{
int b,e,l;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
map[i][j] = INF;
}
map[i][i] = 0;
}
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d",&b,&e,&l);
map[b][e] = map[e][b] = min(map[b][e],l);
}
int ans = floyd();
if ( ans >= INF )
{
printf("No solution.");
}
else
{
printf("%d",ans);
}
}
int main()
{
while(scanf("%d %d",&n,&m) != EOF)
{
init();
printf("\n");
}
return 0;
}