这个是一个板子题哎, 就是倍增然后floyed跑一下。

但是时间限制是30s, 相对比较宽松的, 所以可以直接\(O(n^4)\)的跑。

不过还是没有偷这个小懒。。

传送门

题目大意

求一个点数最少的负环, 输出点数。

解题报告

\(f[i][j][k]\)表示\(i\)\(j\)经过\(k\)个点的最短路。

枚举\(k\)\(i\), 如果存在\(f[i][j][k]\)是负数, 那么就是一个负环。

可以发现这个\(k\)不需要枚举,满足二分的性质,实际上进行倍增是非常科学的。

复杂度是\((n^3\log n)\)的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
const int N=310;
const int lg=10;
int n,m,f[lg][N][N],g[N][N],h[N][N],as;
inline void cmin(int &x,int a) { x=a<x?a:x; }
int main() {
scanf("%d%d",&n,&m); int u,v,w,l;
memset(h,127/3,sizeof(h));
memset(f,127/3,sizeof(f));
rep(i,1,n) f[0][i][i]=h[i][i]=0;
rep(i,1,m) scanf("%d%d%d",&u,&v,&w),f[0][u][v]=w;
for (l=1;l<=9;++l) { bool flag=0;
rep(k,1,n) rep(i,1,n) rep(j,1,n)
cmin(f[l][i][j],f[l-1][i][k]+f[l-1][k][j]);
rep(i,1,n) if (f[l][i][i]<0) flag=1;
if (flag) break; if((1<<l)>=n) return puts("0"), 0;
}
as=0;
while (~l) { memcpy(g,h,sizeof(h)); bool flag=0;
rep(k,1,n) rep(i,1,n) rep(j,1,n)
cmin(h[i][j],g[i][k]+f[l][k][j]);
rep(i,1,n) if (h[i][i]<0) flag=1;
if (flag) memcpy(h,g,sizeof(g));
else as+=(1<<l); -- l;
}
return printf("%d\n",as+1),0;
}

留言