bzoj 4773 负环（floyd倍增）

题意：黎瑟的算法又出错了。对于边带权的有向图 G = (V, E)，请找出一个点数最小的环，使得环上的边权和为负数。保证图中不包含重边和自环。2 <= n <= 300。

思路：容易得到dp[i][j][k]：i到j走k步的最短距离。长得就很像floyd倍增，要使用倍增，显然这个地方要有个类单调性，我们加入i->i，cost=0这种边，使其满足：如果i到j走x步有负环，则走多于x步时也有负环（相当于自己走自己）。然后写出初始矩阵，倍增dp[i][j][k]：i到j走2k步的最短距离。

#include <bits/stdc++.h>
using namespace std;
const int msize = 300 + 5;
const int INF = 0x3f3f3f3f;
int n, m;

struct Matrix
{
    int v[msize][msize];
    Matrix operator * (const Matrix &other)const
    {
        Matrix ret;
        memset(ret.v, INF, sizeof(ret.v));
        for(int k = 1; k <= n; k++)
        {
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= n; j++)
                {
                    ret.v[i][j] = min(ret.v[i][j], v[i][k] + other.v[k][j]);
                }
            }
        }
        return ret;
    }
};
Matrix sta[15], cur;

bool have_negative(Matrix temp)
{
    for(int i = 1; i <= n; i++)
    {
        if(temp.v[i][i] < 0)    return true;
    }
    return false;
}
int main()
{
    memset(cur.v, INF, sizeof(cur.v));
    memset(sta[0].v, INF, sizeof(sta[0].v));


    scanf("%d%d", &n, &m);
    while(m--)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        sta[0].v[u][v] = w;
    }
    for(int i = 1; i <= n; i++) cur.v[i][i] = sta[0].v[i][i] = 0;
    for(int i = 1; i <= log2(n); i++)    sta[i] = sta[i-1] * sta[i-1];


    int ans = 0;
    for(int i = log2(n); i >= 0; i--)
    {
        if(have_negative(cur * sta[i]) == 0)
        {
            cur = cur * sta[i];
            ans += (1 << i);
        }
    }
    printf("%d\n", have_negative(cur * sta[0]) ? ans + 1 : 0);
    return 0;
}