uoj32 跳蚤公路题解

题目链接

点击打开链接

题目解法

首先问题等价于有一个负环可以到 \(v\)
假设环边的 \(w\) 之和为 \(b\)，\(c\) 之和为 \(k\)，则这个环的长度就为 \(kx+b\)
如果是负环，需要满足 \(kx+b<0\)
钦定负环上的一个点 \(st\)，令 \(f_{i,j}\) 表示从 \(st\) 到 \(i\) 的路径中，\(\sum c=j\) 的最小的 \(\sum w\)
但这样做复杂度要到 \(O(n^5)\)

换一个角度思考问题
先考虑普通图 \(bellman-ford\) 找负环的本质，即一个点 \(x\) 被松弛 \(n\) 次就存在负环经过 \(x\)
令 \(f_{i,j}\) 表示至多经过 \(i\) 条边，到点 \(j\) 的最小距离，则有负环的形式化表达是 \(f_{n,x}<f_{n-1,x}\)

把这个式子融合到这道题中
令 \(f_{i,j,k}\) 为到点 \(i\)，经过了 \(j\) 条边，\(\sum c=k\) 的 \(\sum w\) 的最小值
考虑算出每个点可能有负环的范围

具体细节比较复杂，说不清，看代码应该比较容易看懂
时间复杂度 \(O(n^3)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=110;
const LL inf=2e18;
int n,m;
LL f[N][N][N<<1];
bool can[N][N];
typedef tuple<int,int,int> tup;
vector<tup> G[N];
typedef pair<LL,LL> pll;
vector<pll> range[N];
int cur;
void trans(int u){
    can[cur][u]=1;
    for(auto [v,w,s]:G[u]) if(!can[cur][v]) trans(v);
}
LL floordiv(LL x,LL y);
LL ceildiv(LL x,LL y);
LL floordiv(LL x,LL y){
    if(x%y==0) return x/y-1;
    if(y<0) x*=-1,y*=-1;
    if(x>0) return x/y;
    return -ceildiv(-x,y);
}
LL ceildiv(LL x,LL y){
    if(x%y==0) return x/y+1;
    if(y<0) x*=-1,y*=-1;
    if(x>0) return x/y+1;
    return -floordiv(-x,y);
}
int main(){
    read(n),read(m);
    F(i,1,m){
        int x,y,w,s;read(x),read(y),read(w),read(s);
        G[x].pb({y,w,s});
    }
    F(i,1,n) F(j,0,n) F(k,0,n<<1) f[i][j][k]=inf;
    f[1][0][n]=0;
    F(tote,0,n-1)
        F(u,1,n) F(x,0,n<<1) if(f[u][tote][x]!=inf){
            chkmin(f[u][tote+1][x],f[u][tote][x]);
            for(auto [v,w,s]:G[u]) chkmin(f[v][tote+1][x+s],f[u][tote][x]+w);
        }
    F(i,1,n) F(j,-n,n) if(f[i][n][j+n]!=inf){
        LL le=-inf,ri=inf;bool fl=1;
        F(k,-n,n) if(f[i][n-1][k+n]!=inf){
            LL det=f[i][n][j+n]-f[i][n-1][k+n];
            //(k-j)x>det
            if(k-j==0){ if(det>=0) fl=0;}
            else if(k-j<0) chkmin(ri,floordiv(det,k-j));
            else chkmax(le,ceildiv(det,k-j));
        }
        if(le<=ri&&fl) range[i].pb({le,ri});
    }
    F(i,1,n) cur=i,trans(i);
    F(i,1,n){
        vector<pll> banr;
        F(j,1,n) if(can[j][i]) for(auto [l,r]:range[j]) banr.pb({l,r});
        sort(banr.begin(),banr.end());
        LL ans=0,rr=-inf-5;
        for(auto [l,r]:banr){
            if(l>rr) ans+=r-l+1,rr=r;
            else if(r>rr) ans+=r-rr,rr=r;
        }
        ans=inf+inf+1-ans;
        if(ans>1e18) puts("-1");
        else printf("%lld\n",ans);
    }
    return 0;
}