使用floyd可以求解最小环问题.
单纯需要求出最小环长度,方法显而易见
然而,如果需要统计最小环的个数,就比较麻烦.
记\(cnt_{i,j}\)表示从\(i\)到\(j\)的最短路条数.
进行转移.
时间复杂度\(O(n^3)\)
mi=0x3f3f3f3f3f3f3f3f;
rep(k,1,n)
{
rep(i,1,k-1)
rep(j,1,i-1)
{
ll tmp=(ll)dis[i][j]+vl[i][k]+vl[k][j];
if ((tmp<mi) && (tmp<inf))
{
mi=tmp;
ans=cnt[i][j];
}
else if (tmp==mi)
ans+=cnt[i][j];
}
rep(i,1,n)
rep(j,1,n)
if (dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
cnt[i][j]=cnt[i][k]*cnt[k][j];
}
else if (dis[i][j]==dis[i][k]+dis[k][j])
cnt[i][j]+=cnt[i][k]*cnt[k][j];
}
标签:tmp,图论,rep,个数,最小,floyd,ll
From: https://www.cnblogs.com/xu2006/p/16897341.html