【BZOJ4773】负环-倍增+Floyd
程序员文章站
2022-05-22 15:02:32
...
测试地址:负环
做法: 本题需要用到倍增+Floyd。
我们很快能想出的算法:令为走条边,从走到的路径中最小的权值和。从小到大枚举转移即可。
然而并过不了,而且我们发现,负环的长度似乎也不是单调的,即存在长为的负环,不一定表示存在长为的负环。实际上,我们只要给每个点加一个边权为的自环,就可以解决这个问题了。
发现这个性质单调后,我们有两种思路:一是二分答案,二是倍增。但我们发现二分答案需要构造走步时的邻接矩阵(也就是上面写的组成的矩阵),和上面相比复杂度没有区别,因此我们排除这一思路,考虑倍增。
要使用倍增,需要明确一个问题:我们知道行走分两个阶段,得到第一个阶段和第二个阶段的邻接矩阵,如何把它们合并为整个行走的邻接矩阵呢?这时,我们可以使用一种类似Floyd,也类似于矩阵乘法的一个算法,即枚举中间点,然后枚举整个过程的起点和终点转移。我们发现这个东西和矩阵乘法非常类似,它也和矩阵乘法一样满足结合律,但不满足交换律,因此我们采用类似矩阵快速幂的倍增算法,先处理出走次的邻接矩阵,然后从高到低枚举,如果当前行走的矩阵与走次的邻接矩阵合并后,图中没有出现负环,则把当前行走的矩阵与走次的矩阵合并作为新的当前行走的矩阵,即表示走了步。最后,算法中行走的步数就是答案。注意答案比大时,显然就表示无解。于是我们就以的时间复杂度解决了这一题。
以下是本人代码:
#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;
}
上一篇: 费用流
下一篇: 电商企业如何做软文营销推广?