BZOJ 4773 负环

题目大意

给你一个有向图，求点数最小的边权和为负数的环。

这题因为和点以及边都有关系，而且点数小的吓人所以可以考虑使用倍增Floyd。

在倍增Floyd后得到了$dis_{k,i,j}$表示走$\le 2^k$条边从i到j的最短距离。

本来是严格的之后不会做，指点后发现其实这个东西可以设的宽松一点的……之后就惊奇的发现这个东西是单调的了。

对于二进制+单调有两种做法：一种是倍增，使用类似LCA的方法可以枚举到所有的点；第二种是二分。

这里使用二进制倍增的方法。二进制倍增的时候我竟然特判了每一位是不是N的组成部分……倍增LCA也不这样啊……千万不能写啊qwq

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,lg[310],ans,ix,iy,iz;
struct dist
{
    int v[310][310];
    dist() {memset(v,0x3f,sizeof v);}
    dist operator*(const dist &tx)const
    {
        dist ret;
        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]+tx.v[k][j]);
        return ret;
    }
}dis[15],res;
bool check(dist &tx)
{
    for(int i=1;i<=n;++i) if(tx.v[i][i]<0) return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) dis[0].v[i][i]=res.v[i][i]=0;
    for(int i=1;i<=m;++i) scanf("%d%d%d",&ix,&iy,&iz),dis[0].v[ix][iy]=iz;
    for(int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=lg[n];++i) dis[i]=dis[i-1]*dis[i-1];
    for(int i=lg[n];~i;i--)
    {
        dist tmp=dis[i]*res;
        if(!check(tmp)) res=tmp,ans+=(1<<i);
    }
    res=res*dis[0];
    if(!check(res)) ans=-1;
    printf("%d\n",ans+1);
    return 0;
}