[BZOJ4773]负环
题目大意:
给定一个\(n(n\le300)\)个点的简单有向图,求经过点数最小的负环。
思路:
\(f[k][i][j]\)表示从\(i\)到\(j\),经过至多\(2^k\)条边时,边权和的最小值,然后二分即可。
时间复杂度\(\mathcal O(n^3\log n)\)。
源代码:
#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) neg|=ch=='-';
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return neg?-x:x;
}
const int N=301,K=10;
int n,m,f[K][N][N],tmp[2][N][N];
inline void upd(int &a,const int &b) {
a=std::min(a,b);
}
inline void reset(int f[N][N]) {
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=n;j++) {
f[i][j]=i==j?0:INT_MAX;
}
}
}
inline void copy(int f[N][N],int g[N][N]) {
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=n;j++) {
g[i][j]=f[i][j];
}
}
}
inline bool check() {
for(register int i=1;i<=n;i++) {
if(tmp[1][i][i]<0) return true;
}
return false;
}
signed main() {
n=getint(),m=getint();
reset(f[0]);
for(register int i=0;i<m;i++) {
const int u=getint(),v=getint();
f[0][u][v]=getint();
}
for(register int l=1;l<K;l++) {
copy(f[l-1],f[l]);
for(register int k=1;k<=n;k++) {
for(register int i=1;i<=n;i++) {
if(f[l-1][i][k]==INT_MAX) continue;
for(register int j=1;j<=n;j++) {
if(f[l-1][k][j]==INT_MAX) continue;
upd(f[l][i][j],f[l-1][i][k]+f[l-1][k][j]);
}
}
}
}
int ans=INT_MAX;
reset(tmp[0]);
for(register int l=K-1,now=0;l>=0;l--) {
reset(tmp[1]);
copy(tmp[0],tmp[1]);
for(register int k=1;k<=n;k++) {
for(register int i=1;i<=n;i++) {
if(tmp[0][i][k]==INT_MAX) continue;
for(register int j=1;j<=n;j++) {
if(f[l][k][j]==INT_MAX) continue;
upd(tmp[1][i][j],tmp[0][i][k]+f[l][k][j]);
}
}
}
if(check()) {
ans=std::min(ans,now|(1<<l));
} else {
now|=1<<l;
copy(tmp[1],tmp[0]);
}
}
printf("%d\n",ans==INT_MAX?0:ans);
return 0;
}