【UOJ#32】【UR#2】跳蚤公路
最短路，负环，不等式计算
题目大意：
给定一张有向图，每条边有三种颜色（红，白，绿）以及边权。
现在要选定整数 $x$，使每条红边的边权增加 $x$，每条绿边的边权减少 $x$。
要求对于所有 $v\in [1,n]$，求出有多少个整数 $x$，满足从 $1$ 到 $v$ 存在一条路径，使得边权和为负无穷大（即经过了负环）。
若满足条件的 $x$ 超过 $10^{30}$ 个（可以理解为无穷多个），则输出 -1。
题解：
在没有负环的图中，两点间的最短路最多只会经过一个点 $1$ 次，即最多经过 $n-1$ 条边。
Bellman-Ford 算法判断负环的原理就是，每个点松弛 $n-1$ 次后，若还能进行第 $n$ 次松弛来更新最短路，即说明存在负环。
令 $f[i][u][k]$ 表示 $x=0$ 时，经过了最多 $i$ 条边，从 $1$ 号点到 $u$ 号点，经过的红边减去绿边条数为 $k$ 时的最短路。
这个 $f$ 可以通过 Bellman-Ford 算法在 $O(n^4)$ 的时间复杂度内求出。
那么经过 $i$ 条边时，实际的最短路就可以表示为 $kx+f[i][u][k]$。
那么对于点 $u$，若 $u$ 不在负环上，则必然满足：
考虑求它的解集的补集，即 $u$ 在负环上的情况。
那么相当于对一个 $v$ ，满足 $\min\{kx+f[n-1][u][k]\}\leq vx+f[n][u][v]$，对每个 $k$ 求出的解求交即可。注意上下取整的问题。
然后再对每个 $v$ 求得的解集求并集，就是 $u$ 在负环上时的 $x$ 的解。
然后这个负环要更新到其他的点。$u$ 能到的所有点都可以经过这个负环，所以对于 $u$ 求出的 $x$ 的解要更新到 $u$ 能到的点。
对于两点间的连通性只需要一次传递闭包即可，最后对每个点求一个线段覆盖长度的问题。
算法的总时间复杂度 $O(n^4)$。
Code：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cstring>
using namespace std;
typedef long long LL;
typedef pair<LL,LL>PII;
#define f(a,b,c) F[a][b][(c)+102]
const int N=105;
const LL inf=2e18;
struct edge{
int to,nxt,w,s;
}e[N*N];
int head[N],cnt,n,m;
bool go[N][N];
LL F[N][N][2*N];
vector<PII>sg[N];
PII calc(int a,LL b){
if(a==0){
if(b>0)return make_pair(-inf,inf);
return make_pair(inf,-inf);
}
if(a>0){
LL up=b/a;
while(up*a>=b)--up;
return make_pair(-inf,up);
}
b=-b,a=-a;
LL dn=b/a-1;
while(dn*a<=b)++dn;
return make_pair(dn,inf);
}
inline PII un(const PII&a,const PII&b){
return make_pair(max(a.first,b.first),min(a.second,b.second));
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(cin>>n>>m;m--;){
int u,v,w,s;
cin>>u>>v>>w>>s;
e[++cnt]=(edge){v,head[u],w,s},head[u]=cnt;
go[u][v]=1;
}
for(int i=1;i<=n;++i)go[i][i]=1;
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
go[i][j]|=go[i][k]&&go[k][j];
for(int i=0;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=-n;k<=n;++k)f(i,j,k)=inf;
f(0,1,0)=0;
for(int t=0;t<n;++t){
memcpy(F[t+1],F[t],sizeof*F);
for(int i=1;i<=n;++i)
for(int j=head[i];j;j=e[j].nxt){
const int to=e[j].to;
for(int k=-n;k<=n;++k)
if(f(t,i,k)<inf)
f(t+1,to,k+e[j].s)=min(f(t+1,to,k+e[j].s),f(t,i,k)+e[j].w);
}
}
for(int x=1;x<=n;++x)if(go[1][x]){
vector<PII>d;
for(int k0=-n;k0<=n;++k0)if(f(n,x,k0)<inf){
PII vc=make_pair(-inf,inf);
for(int k1=-n;k1<=n;++k1)
if(f(n-1,x,k1)<inf)
vc=un(vc,calc(k0-k1,f(n-1,x,k1)-f(n,x,k0)));
if(vc.first<=vc.second)d.push_back(vc);
}
for(int y=1;y<=n;++y)
if(go[x][y]){
for(int i=0;i<(int)d.size();++i)
sg[y].push_back(d[i]);
}
}
for(int x=1;x<=n;++x){
if(!go[1][x]){cout<<"-1\n";continue;}
if(sg[x].empty()){cout<<"-1\n";continue;}
sort(sg[x].begin(),sg[x].end());
LL ans=0;
PII nw=sg[x][0];
for(int i=1;i<(int)sg[x].size();++i){
PII nx=sg[x][i];
if(nx.first>nw.second){
ans+=nw.second-nw.first+1;
nw=nx;
}else nw.second=max(nw.second,nx.second);
}
ans+=nw.second-nw.first+1;
ans=2*inf+1-ans;
cout<<(ans>1e18?-1:ans)<<'\n';
}
return 0;
}