Description

在忘记考虑负环之后，黎瑟的算法又出错了。对于边带权的有向图 G = (V, E)，请找出一个点数最小的环，使得

环上的边权和为负数。保证图中不包含重边和自环。

Input

第1两个整数n, m,表示图的点数和边数。

接下来的m行，每<=三个整数ui, vi, wi，表<=有一条从ui到vi，权值为wi的有向边。

2 <= n <= 300

0 <= m <= n(n <= 1)

1 <= ui, vi <= n

|wi| <= 10^4

Output

仅一行一个整数，表示点数最小的环上的点数，若图中不存在负环输出0。

Sample Input

3 6

1 2 -2

2 1 1

2 3 -10

3 2 10

3 1 -10

1 3 10

Sample Output

2

分析：

求负环：

A：bellmax ford

B：floyed

C：spfa（扔下去。。。）

设计状态

f[k][i][j]表示i到j经过k个点的最短路

枚举k和i,

如果存在f[k][i][i]是负数， 那么就是一个负环

k可以通过倍增得到:f[k]<—f[k-1],f[k-1]

这只是基本原理

具体实现有一些细节

其实我们需要进行两次floyed

第一次利用倍增的方法

维护好f[k][i][j]

f[k][i][j]=min(f[k-1][i][l]+f[k-1][l][j]);

但是这样的话我们只知道走2^k步时的答案

想想第一次接触倍增是什么时候

没错，LCA

那时候我们是怎么处理的呢

for (i=lg;i>=0;i–)

这就相当于把答案二进制分解了

得出的答案+1就是最终答案

这道题也是一样

我们要求的是不存在负环的最大步数，

最大步数+1即为答案

第一次floyed我们得到了一个k（走2^k出现负环）

那答案一定<=2^k

我们就把k从大到小循环

只要是f[k][i][i]>0

ans+=(1 << k)

当然还有一些细节要处理

还记得我们一开始记录了一个h邻接矩阵

在循环的开始

我们先调用一个全新的函数：memecpy(a,b,sizeof(b))

表示b中的信息全部复制到a

这个while循环我们可以一步一步看

首先memcpy，g保存一下h数组的信息

设g记录了走x步时的floyed的答案

之后就进行了一次耳熟能详的floyed

用来判断在走2^k+x步数的情况下

能不能走出负环，

能：把h数组的信息还原（这个2^k+x太大了，不符合我们找最大非负环的限制）

不能：ans+=(1 << k)，h数组中的信息保留(走2^k+x)

这个h/g数组就相当于记录没有负环的最大步数

ans记录走了多少步

最后输出ans+1

tip

变量名不要搞错了

这里写代码片#include
     
      #include
      
       #include
       
        using namespace std;const int N=310;const int lg=10;int n,m,f[lg][N][N],g[N][N],h[N][N],ans;void floyed(){    int i,j,k,l;    for (k=1;k
        
         =n)  //整张图都不存在负环         {            puts("0");            return;        }    }    ans=0;    while (k>=0)  //步数    {        memcpy(g,h,sizeof(h));        bool ff=0;        for (l=1;l<=n;l++)            for (i=1;i<=n;i++)                for (j=1;j<=n;j++)                    h[i][j]=min(h[i][j],g[i][l]+f[k][l][j]);        for (i=1;i<=n;i++)            if (h[i][i]<0) ff=1;        if (ff) memcpy(h,g,sizeof(g));  //恢复信息         else ans+=(1<