4898: [Apio2017]商旅

2024-03-27 04:48

文章标签 商旅 apio2017 4898

本文主要是介绍4898: [Apio2017]商旅，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

发现实际上把每个物品提出来做最短路后，可以转化为一个在图中求最小的 $\frac{\sum{w}}{\sum{time}}$ 的环
上面那东西就是个01规划搞搞就行了，然后最小环直接套floyd即可
c++代码如下：


#include<bits/stdc++.h>
#define eps 1e-2
#define rep(i,x,y) for(register int i = x; i <= y; ++ i )
#define repd(i,x,y) for(register int i = x ; i >= y; -- i )
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{
    char c;int sign = 1; x = 0;
    do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));
    do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));
    x *= sign;
}const int N = 101,M=1e3+80;
ll dis[N][N],di[N][N],s[N][M],b[N][M],n,m,K;
double d[N][N];inline bool check(double w )
{
    rep(i,1,n) rep(j,1,n) d[i][j] = 1e9;
    rep(i,1,n) rep(j,1,n) 
        d[i][j] = min(d[i][j],dis[i][j]*w - di[i][j] );    rep(k,1,n)
        rep(i,1,n)
            rep(j,1,n)
                d[i][j] = min(d[i][j],d[i][k] + d[k][j]);    rep(i,1,n) if(d[i][i] < 0) return true;
    return false;
}int main()
{
    read(n); read(m); read(K);
    rep(i,1,n) rep(j,1,n) dis[i][j] = 1e9;
    rep(i,1,n) rep(j,1,K) read(s[i][j]),read(b[i][j]);
    rep(i,1,m)
    {
        int v,w,p;
        read(v); read(w); read(p);
        dis[v][w] = p;
    }    rep(k,1,n) rep(i,1,n) rep(j,1,n) 
        dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);    rep(i,1,n) rep(j,1,n) rep(k,1,K)
        if(s[i][k] != -1 && b[j][k] != -1)
            di[i][j] = max(di[i][j],b[j][k] - s[i][k]);    double l = 0,r = 1e18,mid,ans;
    while(fabs(r-l) > eps)
    {
        if(check(mid = (l + r) / 2 )) l = mid,ans = mid;
        else r = mid;
    }    printf("%.0lf",ans-0.5);        return 0;
}