【BZOJ4773】负环
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
1 2 -2
2 1 1
2 3 -10
3 2 10
3 1 -10
1 3 10
Sample Output
2
题解:我承认最近做矩乘有点多了~
看时间复杂度显然是O(n³㏒n)可以搞的,所以直接上倍增Floyd,具体方法有点像用倍增求LCA。就是先预处理出邻接矩阵的2次方,4次方,2^n次方。。。然后在不断从大到小去试,如果ans*转移矩阵的2^j次方不存在负环,则ans就乘上邻接矩阵的2^j次方,否则不乘。最后只要在乘上邻接矩阵的一次方,就一定会出现负环了
但仔细思考这个方法,发现貌似不满足单调性,也就是可能存在长度为5的负环,却不存在长度为6的负环,因此我们只要连一条从i到i长度为0的边,即让邻接矩阵的map[i][i]=0,就可以使它满足单调性了(其实正常的邻接矩阵都应该这么搞~)
听说O(n³㏒²n)也能过,难道是我的代码自带大常数?跑了7000多ms~
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,ans;
typedef struct matrix
{
int v[310][310];
}M;
M f[12],x,y,emp;
M mmul(M a,M b)
{
M c=emp;
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
c.v[i][j]=min(c.v[i][j],a.v[i][k]+b.v[k][j]);
return c;
}
int main()
{
scanf("%d%d",&n,&m);
memset(emp.v,0x3f,sizeof(emp.v));
f[0]=x=emp;
int i,a,b,c,j;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
f[0].v[a][b]=c;
}
for(i=1;i<=n;i++) f[0].v[i][i]=x.v[i][i]=0;
for(j=1;(1<<j)<=n;j++)
f[j]=mmul(f[j-1],f[j-1]);
for(j=j-1;j>=0;j--)
{
y=mmul(x,f[j]);
for(i=1;i<=n;i++)
if(y.v[i][i]<0) break;
if(i==n+1) x=y,ans+=(1<<j);
}
if(ans>n) printf("0");
else printf("%d",ans+1);
return 0;
}