书上Floyd的做法很巧妙,寻找答案的办法类似DP:记录前驱回溯。不过,本题 $n$ 很小,暴搜DFS的做法时间复杂度相同,实现比较简单(蒟蒻不会图论,随便糊了个)。
算法
(暴力枚举 ) $O(n^3)$
void dfs(int s,int x,int siz) //s:环的起点 x:当前遍历到的点 siz:已经访问的点数
{
if (dist>=ans) return; //剪枝,当前答案大于等于之前的答案就没有用,可以回溯
if (x==s) //回到起点
{
if (siz>0) //siz=0表示从起点出发
{
if (siz>=3)
{
if (dist<ans) //更新
{
ans=dist;
len=siz;
for(int i=1;i<=len;++i) q[i]=p[i];
}
}
return;
}
}
for(int y=1;y<=n;++y)
if (x!=y&&!v[y])
{
v[y]=1;
dist+=a[x][y];
p[siz+1]=y;
dfs(s,y,siz+1);
p[siz+1]=0;
dist-=a[x][y];
v[y]=0;
}
}
注意有关环的搜索,如何表示只有一个点/转回起点的不同状态。注意回溯时撤销操作。
时间复杂度
主程序枚举 s=1..n 进行搜索,最多搜 $n$ 层,用邻接矩阵存图,DFS复杂度 $O(n^2)$ ,总时间复杂度 $O(n^3)$ 。
牛