bzoj4773: 负环

题解：

网上还有一种spfa+深度限制的算法

https://www.cnblogs.com/BearChild/p/6624302.html

是不加队列优化的spfa，我觉得复杂度上限是bellman-ford nm的，另外从每个点跑加上二分答案所以是n^2mlogn的

但实测的确是挺快的，可能是深度限制的原因

这题可以用倍增floyd

比较慢的就是二分+倍增floyd是n^3log^2n的

可以直接用找lca的思想，做到n^3logn

不太懂floyd的理论

两个矩阵算起来的时候要用新矩阵去更新的

c[i][j]=min(c[i][j],a[i][k]+b[k][j])这样做

然后卡了一下常（指针）

不过在bz上效果好像不是很明显

自己测试还是很明显得

不过windos下数组极慢，要用5.5s

linux下只用了2s，指针的win和linux下几乎相同都是1s

代码：

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (rint i=h;i<=t;i++)

#define dep(i,t,h) for (rint i=t;i>=h;i--)

const int INF=1e9;

const int N=;

char ss[<<],*A=ss,*B=ss;

IL char gc()

{

  return (A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++);

}

template<class T>void read(T &x)

{

  rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;

  while (c=gc(),<c&&c<) x=(x<<)+(x<<)+(c^); x*=f;

}

int f[][N][N],t[N][N],t1[N][N],n,m;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  read(n); read(m);

  rep(k,,)

  rep(i,,n)

    rep(j,,n)

      if (i!=j)

        f[k][i][j]=INF;

  rep(i,,m)

  {

    int x,y,z;

    read(x); read(y); read(z);

    if (f[][x][y]>z) f[][x][y]=z;

  }

  rep(i,,)

  {

    rep(i1,,n)

      rep(i2,,n)

      {

        rint tmp=f[i-][i2][i1];

        rint *p1=f[i-][i1];

        rep(i3,,n)

        {

          rint *p3=f[i][i2];

          rint p4=p3[i3];

          rint p2=tmp+p1[i3];

          if (p4>p2) p3[i3]=p2;

        }

      }

  }

  rep(i,,n)

    rep(j,,n)

      t[i][j]=f[][i][j];

  int ans=;

  dep(i,,)

  {

    rep(i1,,n)

      rep(i2,,n)

        t1[i1][i2]=INF;

    rep(i1,,n)

    {

      rint (*g)=f[i][i1];

      rep(i2,,n)

      {

        rint tmp=t[i2][i1];

        rint *p3=t1[i2];

        rep(i3,,n)

        {

          rint p1=p3[i3];

          rint p2=tmp+g[i3];

          if (p1>p2) p3[i3]=p2;

        }

      }

    }

    bool tt=;

    rep(j,,n)

      if (t1[j][j]<) tt=;

    if (!tt)

    {

      ans+=<<i;

      memcpy(t,t1,sizeof(t1));

    }

  }

    if (ans+==) cout<<<<endl;

  else cout<<ans+<<endl;

  return ;

}

巴特西

bzoj4773: 负环

最新文章

热门文章