欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ4773: 负环

程序员文章站 2022-05-22 15:05:34
...

可以倍增floyd,倍增判断走2^i步是否存在负环就好了。

其实和3763是一样的,然而那题数据挂了。

#include<cstdio>
inline void upd1(int&a,int b){
	a>b?a=b:0;
}
const int N=301;
typedef int arr[N][N];
int n;
void pre(arr a){
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			a[i][j]=1e9;
}
void dup(arr a,arr b){
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			a[i][j]=b[i][j];
}
bool jud(arr a){
	for(int i=1;i<=n;++i)
		if(a[i][i]<0)return 1;
	return 0;
}
arr c,g,f[9];
void mul(arr a,arr b){
	pre(c);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			for(int k=1;k<=n;++k)
				upd1(c[i][k],a[i][j]+b[j][k]);
}
int m,u,v,w,s,l;
int main(){
	scanf("%d%d",&n,&m);
	pre(f[0]);
	for(int i=1;i<=n;++i)
		f[0][i][i]=0;
	while(m--){
		scanf("%d%d%d",&u,&v,&w);
		f[0][u][v]=w;
	}
	for(s=1;;++s){
		mul(f[s-1],f[s-1]);
		if(jud(c))break;
		if(1<<s>=n)
			return!~puts("0");
		dup(f[s],c);
	}
	dup(g,f[--s]),l=1<<s;
	while(s){
		mul(g,f[--s]);
		if(!jud(c))
			dup(g,c),l|=1<<s;
	}
	printf("%d\n",l+1);
}