题解 P3778 【[APIO2017]商旅】

· · 题解

首先这题并不卡精度。二分的时候只二分整数就没有任何问题了。。。

裸分数规划+Folyd, 预处理出任意两点的距离g[i][j]，预处理在i点买某个东西到j点卖出的最大获益earn[i][j],然后二分收益r率。把两点的距离重新定义为w[i][j]=earn[i][j]-r*g[i][j]。跑个Floyd，然后判断是否 \max w[i][i]\geq 0，即是否有正环即可。

#include <iostream>
#define ll long long
using namespace std;
int const N=101,K=1001,L=8;
ll const INF=1e9;
int n,m,t;
ll s[N][K],b[N][K],earn[N][N],g[N][N],f[N][N];
bool find(ll r){    
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i==j) f[i][j]=-INF; else f[i][j]=earn[i][j]-r*g[i][j];
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                f[i][j]=max(f[i][j],f[i][k]+f[k][j]);
    ll now=-INF;
    for (int i=1;i<=n;i++) now=max(now,f[i][i]);
    return now>=0;
}
ll get(){
    ll l=1,r=1e9;
    while (l<r-1){
        ll mid=(l+r)/2;
        if (find(mid)) l=mid; else r=mid-1;
    }
    if (find(r)) return r;
    if (find(l)) return l;
    return l-1;
}
int main(){
    cin>>n>>m>>t;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=t;j++){
            cin>>b[i][j]>>s[i][j];
            if (b[i][j]==-1) b[i][j]=INF;
            if (s[i][j]==-1) s[i][j]=0;
        }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            for (int k=1;k<=t;k++)
                earn[i][j]=max(earn[i][j],s[j][k]-b[i][k]);
    for (int i=1;i<=m;i++){
        int x,y;
        ll z;
        cin>>x>>y>>z;
        g[x][y]=z;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (!g[i][j]) g[i][j]=INF;
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (!g[i][j] || g[i][k]+g[k][j]<g[i][j]) g[i][j]=g[i][k]+g[k][j];

    cout<<get()<<endl;
    return 0;
}