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

【BZOJ4773】负环-倍增+Floyd

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

测试地址:负环
做法: 本题需要用到倍增+Floyd。
我们很快能想出O(n2m)O(n^2m)的算法:令f(i,j,k)f(i,j,k)为走ii条边,从jj走到kk的路径中最小的权值和。从小到大枚举ii转移即可。
然而并过不了,而且我们发现,负环的长度似乎也不是单调的,即存在长为kk的负环,不一定表示存在长为k+1k+1的负环。实际上,我们只要给每个点加一个边权为00的自环,就可以解决这个问题了。
发现这个性质单调后,我们有两种思路:一是二分答案,二是倍增。但我们发现二分答案需要构造走ii步时的邻接矩阵(也就是上面写的f(i,j,k)f(i,j,k)组成的矩阵),和上面相比复杂度没有区别,因此我们排除这一思路,考虑倍增。
要使用倍增,需要明确一个问题:我们知道行走分两个阶段,得到第一个阶段和第二个阶段的邻接矩阵,如何把它们合并为整个行走的邻接矩阵呢?这时,我们可以使用一种类似Floyd,也类似于矩阵乘法的一个算法,即枚举中间点kk,然后枚举整个过程的起点ii和终点jj转移。我们发现这个东西和矩阵乘法非常类似,它也和矩阵乘法一样满足结合律,但不满足交换律,因此我们采用类似矩阵快速幂的倍增算法,先O(n3logn)O(n^3\log n)处理出走2i(i0)2^i(i\ge 0)次的邻接矩阵,然后从高到低枚举ii,如果当前行走的矩阵与走2i2^i次的邻接矩阵合并后,图中没有出现负环,则把当前行走的矩阵与走2i2^i次的矩阵合并作为新的当前行走的矩阵,即表示走了2i2^i步。最后,算法中行走的步数+1+1就是答案。注意答案比nn大时,显然就表示无解。于是我们就以O(n3logn)O(n^3\log n)的时间复杂度解决了这一题。
以下是本人代码:

#include <bits/stdc++.h>
using namespace std;
const int inf=1000000000;
int n,m,finalans=0;
struct matrix
{
	int dis[310][310];
}M[10],E,now,ans;

void mult(matrix A,matrix B,matrix &S)
{
	S=E;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				S.dis[i][j]=min(S.dis[i][j],A.dis[i][k]+B.dis[k][j]);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			E.dis[i][j]=inf;
		E.dis[i][i]=0;
	}
	
	M[0]=E;
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		M[0].dis[x][y]=w;
	}
	for(int i=1;i<=9;i++)
		mult(M[i-1],M[i-1],M[i]);
	
	now=E;
	for(int i=9;i>=0;i--)
	{
		mult(now,M[i],ans);
		bool flag=0;
		for(int j=1;j<=n;j++)
			if (ans.dis[j][j]<0)
			{
				flag=1;
				break;
			}
		if (!flag) finalans+=(1<<i),now=ans;
	}
	if (finalans>n) printf("0");
	else printf("%d",finalans+1);
	
	return 0;
}