判断负环 \(Spfa\) 没什么可变性。考虑 \(bellman\)

\(f(i,x)\) 表示至多用 \(i\) 步走到 \(x\) 的最短路。若则 \(x\) 点不在负环中,应有 \(f(n,x)=f(n-1,x)\)

根据这个思路,设 \(f(i,j,k)\) 表示至多用 \(j\) 走到 \(i\) , \(x\) 系数是 \(k\)\(\sum w\) 的最小值。

\(v\) 不在负环中,需满足 \[ \min_k \{ kx + f(n,v,k) \} \ge \min_j \{ jx + f(n-1,v,j) \} \] 剩下的事情就是解不等式了,一层层打开,求交,求并等等…..

细节较多,但补记转换一下会好写很多。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef long long LL;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=125, maxe=10005;
int fir[maxn],nxt[maxe],son[maxe],w[maxe],vk[maxe],tot;
void add(int x,int y,int w1,int w2){
son[++tot]=y; w[tot]=w1; vk[tot]=w2; nxt[tot]=fir[x]; fir[x]=tot;
}
int n,m,o;
LL f[2][maxn][205],INF;
bool g[maxn][maxn];
typedef pair<LL,LL> PairLL;
PairLL lst[maxn][maxn*2],lst2[maxn*maxn*2];
int cnt[maxn],cnt2;

inline LL get1(LL a,LL b){
if(b<0) a=-a,b=-b;
return a>0 ? a/b : -((-a+b-1)/b);
}
inline LL get2(LL a,LL b){ return -get1(-a,b); }
int main(){
freopen("uoj32.in","r",stdin);
freopen("uoj32.out","w",stdout);
n=getint(); m=getint();
for(int i=1;i<=m;i++){
int x=getint(),y=getint(),w1=getint(),w2=getint();
add(x,y,w1,w2); g[x][y]=true;
}
for(int i=1;i<=n;i++) g[i][i]=true;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) g[i][j]|=g[i][k]&g[k][j];

memset(f,63,sizeof(f)); INF=f[0][0][0]; f[o=0][1][100]=0;
for(int i=1;i<=n;i++){
o^=1; memcpy(f[o],f[o^1],sizeof(f[o]));
for(int k=100-i;k<=100+i;k++)
for(int j=1;j<=n;j++)
if(f[o^1][j][k]<INF)
for(int t=fir[j];t;t=nxt[t])
f[o][son[t]][k+vk[t]]=min(f[o][son[t]][k+vk[t]],f[o^1][j][k]+w[t]);
}

for(int i=1;i<=n;i++)
for(int k=100-n;k<=100+n;k++)
if(f[o][i][k]<INF){
LL L=-INF, R=INF;
for(int j=100-n;j<=100+n;j++)
if(f[o^1][i][j]<INF){
if(j>k) R=min(R,get2(f[o^1][i][j]-f[o][i][k],j-k));
else if(j<k) L=max(L,get1(f[o^1][i][j]-f[o][i][k],j-k));
else if(f[o^1][i][j]<=f[o][i][k]) L=INF, R=-INF;
}
if(L<=R) lst[i][++cnt[i]]=mp(L,R); // printf("%d [%d, %d]\n",i,L,R);
}

for(int v=1;v<=n;v++){
LL L=INF,R=-INF,mR=-INF; int flg=0;
cnt2=0;
for(int i=1;i<=n;i++)
if(g[1][i]&&g[i][v])
for(int j=1;j<=cnt[i];j++) lst2[++cnt2]=lst[i][j];
sort(lst2+1,lst2+1+cnt2);

for(int i=1;i<=cnt2;i++){
if(i==1){
if(lst2[i].X>-INF){ L=-INF; R=lst2[i].X; flg=1; break; }
}
else if(lst2[i].X>=mR){ L=mR; R=lst2[i].X; flg=1; break; }
mR=max(mR,lst2[i].Y);
}
if(!cnt2) L=-INF, R=INF;
else if(!flg&&mR<INF) L=mR, R=INF;
if(L<=R) printf("%lld\n",(L==-INF||R==INF)?-1:R-L+1);
else printf("0\n");

}

return 0;
}