[APIO2017]商旅

佚名 6年前 (2019-05-11) 随笔 695人围观抢沙发百度已收录

洛咕

题意:一张有向图\(N(N<=100)\)个点\(M(M<=10000)\)条边，有\(K(K<=1000)\)种商品，每种商品在每个点有一个买入价格\(b[i]\)和卖出价格\(s[i]\)，也有可能某个点不支持某种商品的买入或卖出.同一时刻只能携带一种商品.求一个回路使得环路的盈利效率(指从环路中得到的收益除以花费的时间)最大,答案向下取整.

分析:\(N\)和\(K\)都很小,我们可以直接\(floyd\)预处理出每两个点之间的最短路\(d[i][j],O(N^3)\),以及每两个点之间的最大收益\(w[i][j],O(N^2K)\).

又是这种比值最大,01分数规划的套路,二分mid,把每条边的边权设为\(mid*d[u][i]-w[u][i]\),然后判定负环就行了.

本题很恶意,超级卡精度,反正我开了\(long\) \(double\)才过.

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
   return s*w;
}
const int N=105;
const int M=1005;
long double eps=1e-10;
int n,m,K;
int b[N][M],s[N][M],w[N][N],d[N][N],visit[N];
long double dis[N];
inline bool dfs(int u,long double mid){
    visit[u]=1;
    for(int i=1;i<=n;i++)
        if(d[u][i]<1e9&&u!=i)
            if(dis[i]>dis[u]+mid*d[u][i]-w[u][i]){
                dis[i]=dis[u]+mid*d[u][i]-w[u][i];
                if(visit[i]||dfs(i,mid))return true;
            }
    visit[u]=0;
    return false;
}
inline bool check(long double mid){
    memset(dis,0,sizeof(dis));
    memset(visit,0,sizeof(visit));
    for(int i=1;i<=n;i++)if(dfs(i,mid))return true;
    return false;
}
int main(){
    n=read();m=read();K=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=K;j++)
            b[i][j]=read(),s[i][j]=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=K;k++)
                if(b[i][k]!=-1&&s[j][k]!=-1)
                    w[i][j]=max(w[i][j],s[j][k]-b[i][k]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            d[i][j]=1e9;
    for(int i=1;i<=n;i++)d[i][i]=0;
    for(int i=1;i<=m;i++){
        int a=read(),b=read(),c=read();
        d[a][b]=c;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    long double l=0.0000,r=10000000000.0000;
    while(r-l>eps){
        long double mid=(l+r)/2.0;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%d\n",(int)r);
    return 0;
}