题意:
给一个无向图带权图,求其中的最小简单环(点数>=3)。
题解:
Floyd变形。
考虑一个环上的所有点,一定有一个编号最大的点;
用Floyd求最小环:u->···->v->k->u,其中k是与u,v均相邻的点。若保证v->u这段不经过k,那么就形成了一个环;
只要k>u,k>v即可保证不经过k。
参考代码:
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e2+9;
const int inf=99999999;
int n,m,cnt;
int mp[MAXN][MAXN],dis[MAXN][MAXN];
int pre[MAXN][MAXN],path[MAXN];
int Floyd()
{
int minV=inf;
for(int k=1; k<=n; k++)
{
for(int i=1; i<k; i++)
for(int j=i+1; j<k; j++)
if(minV>dis[i][j]+mp[j][k]+mp[k][i])
{
minV=dis[i][j]+mp[j][k]+mp[k][i];
int p=j;
cnt=0;
while(p!=i)
{
path[++cnt]=p;
p=pre[i][p];//pre[i][j]记录i->j路线上j的前一个点
}
path[++cnt]=i;
path[++cnt]=k;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(dis[i][j]>dis[i][k]+dis[k][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
pre[i][j]=pre[k][j];
}
}
return minV;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
dis[i][j]=mp[i][j]=inf;
pre[i][j]=i;
}
for(int i=1; i<=m; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
mp[u][v]=min(mp[u][v],w);
dis[u][v]=dis[v][u]=mp[v][u]=mp[u][v];
}
int ans=Floyd();
if(ans!=inf)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%d ",pre[i][j]);
puts("");
}
for(int i=1;i<=cnt;i++)
printf("%d ",path[i]);
}
else
puts("No solution.");
return 0;
}