题目要求我们找出一个包含点数最少的负环，我们考虑最终答案是什么样子的。

手模几组小数据，画画图，发现最终答案一定是个简单环（包含n个点n条边），那么我们可以通过边数确定点数。

我们设 $f_{k,i,j}$ 表示从 $i$ 走到 $j$ 走 $k$ 步的最小值，转移和昨天T4类似。

我们注意到一个结论，对于一个点 $i$ ，我们找到最小的 $l$ 满足 $f_{l,i,i}$ 小于 $0$ ，那么 $l$ 就是以 $i$ 为起点的负环的最小长度。

可以利用反证法证明，如果说 $l$ 不是最小长度的话，那么一定存在一个 $l'$ 满足 $f_{l',i,i}$ 小于0，与前提矛盾了，所以不成立。

而且这个环一定是个简单环，也可以用反证法证明，假设不是简单环，那么这个复杂环里面一定存在一个 $i$ 开头的简单负环，说明也存在一个 $l'$ 满足 $f_{l',i,i}$ 小于0，与前提矛盾，不成立。

最后我们可以利用类似倍增跳 $lca$ 的方法维护。

注意一些实现的小细节，为了保证 $f$ 的单调性（方便倍增），我们要把 $dis_{i,i}$ 赋值为0而不是极大值。

#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define wswlovewbn 5201314
#define INF (1e9)
using namespace std;
const int N=301;
int n,m,S,T,u,v,k,w=0;
struct Martix{
	int p[N][N];
}M[9];
int getmin(int x,int y){
	return x>y?y:x;
}
Martix operator*(const Martix A,const Martix B){
	Martix C;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			C.p[i][j]=INF;
			for(int k=1;k<=n;k++){
				C.p[i][j]=getmin(C.p[i][j],A.p[i][k]+B.p[k][j]);
			}
		}
	}return C;
}
Martix res,nw;
bool check(Martix x){
	for(int i=1;i<=n;i++){
		if(x.p[i][i]<0)return 1;
	}return 0;
}
int ans;
int main(){
//	freopen("ex.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)M[0].p[i][j]=res.p[i][j]=INF;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		M[0].p[u][v]=w;
	}
	for(int i=1;i<=8;i++)M[i]=M[i-1]*M[i-1];
	for(int i=8;i>=0;i--){
		nw=res*M[i];
		if(!check(nw)){
			if(i==8){
				puts("0");return 0;
			}
			res=nw,ans+=(1<<i);
		}
	}
	printf("%d\n",ans+1);
	return 0;
}

bzoj4773

这道题首先我们并不知道我们的答案是多少，考虑倍增

我们设 $dp_{i,j,l}$ 表示从 $i$ 到 $j$ 走 $2^l$ 步的最短路，那我们可以很容易地使用弗洛伊德转移出：

然后我们就可以每次对答案的每一位拆分，跑一边弗洛伊德，如果没跑出负环，即存在 $dp_{i,i,l}<0$ 那么就说明走 $2^k$ 一定走不出去，则答案一定大于等于 $2^k$ ，加上 $2^k$ 即可

初始化的时候一定要让 $dp_{i,i,0}=0$ 然后，不要开long long

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 305
using namespace std;
bool Test_MLE_start;
int _=1,n,m,ans=0,MAXN,dp[N][N][15],h[N][N],g[N][N];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("A.in","r",stdin);
//	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads();memset(dp,0x3f,sizeof(dp));memset(h,0x3f,sizeof(h));
		for(int i=1;i<=n;i++) h[i][i]=0;
		for(int i=1;i<=m;i++){
			int u,v,w;u=reads(),v=reads(),w=reads();
			dp[u][v][0]=min(dp[u][v][0],w);
		}
		for(int l=1;l<9;l++){
			for(int k=1;k<=n;k++){
				for(int i=1;i<=n;i++){
					for(int j=1;j<=n;j++){
						dp[i][j][l]=min(dp[i][j][l],dp[i][k][l-1]+dp[k][j][l-1]);
					}
				}
			}
		}
		for(int l=8;l>=0;l--){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					g[i][j]=h[i][j];
				}
			}
			for(int k=1;k<=n;k++){
				for(int i=1;i<=n;i++){
					for(int j=1;j<=n;j++){
						h[i][j]=min(h[i][j],g[i][k]+dp[k][j][l]);
					}
				}
			}
			bool flg=0;
			for(int i=1;i<=n;i++){
				if(h[i][i]<0) flg=1;
			}
			if(flg){
				for(int i=1;i<=n;i++){
					for(int j=1;j<=n;j++){
						h[i][j]=g[i][j];
					}
				}
			}
			else ans+=(1<<l);
		}
		if(ans==511) puts("0");
		else printf("%lld\n",ans+1);
	}
	return 0;
}