[图论]floyd统计最小环个数

使用floyd可以求解最小环问题.

单纯需要求出最小环长度，方法显而易见

最小环 - OI Wiki (oi-wiki.org)

然而，如果需要统计最小环的个数，就比较麻烦.

记\(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];
    }