首页 > 代码库 > 【BZOJ4773】负环 倍增Floyd
【BZOJ4773】负环 倍增Floyd
【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;}
【BZOJ4773】负环 倍增Floyd
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。