BZOJ4898 & BZOJ5367 & 洛谷3778:[APIO2017]商旅——题解

Wesley13
• 阅读 299

https://www.lydsy.com/JudgeOnline/problem.php?id=4898

https://www.lydsy.com/JudgeOnline/problem.php?id=5367

https://www.luogu.org/problemnew/show/P3778

在广阔的澳大利亚内陆地区长途跋涉后,你孤身一人带着一个背包来到了科巴。你被这个城市发达而美丽的市场所

深深吸引,决定定居于此,做一个商人。科巴有个集市,集市用从1到N的整数编号,集市之间通过M条单向道路连

接,通过每条道路都需要消耗一定的时间。在科巴的集市上,有K种不同的商品,商品用从1到K的整数编号。每个

集市对每种商品都有自己的定价,买入和卖出商品的价格可以是不同的。并非每个集市都可以买卖所有的商品:一

个集市可能只提供部分商品的双向交易服务;对于一种商品,一个集市也可能只收购而不卖出该商品或只卖出而不

收购该商品。如果一个集市收购一种商品,它收购这种商品的数量是不限的,同样,一个集市如果卖出一种商品,

则它卖出这种商品的数量也是不限的。为了更快地获得收益,你决定寻找一条盈利效率最高的环路。环路是指带着

空的背包从一个集市出发,沿着道路前进,经过若干个市场并最终回到出发点。在环路中,允许多次经过同一个集

市或同一条道路。在经过集市时,你可以购买或者卖出商品,一旦你购买了一个商品,你需要把它装在背包里带走

。由于你的背包非常小,任何时候你最多只能持有一个商品。在购买一个商品时,你不需要考虑你是否有足够的金

钱,但在卖出时,需要注意只能卖出你拥有的商品。从环路中得到的收益为在环路中卖出商品得到的金钱减去购买

商品花费的金钱,而一条环路上消耗的时间则是依次通过环路上所有道路所需要花费的时间的总和。环路的盈利效

率是指从环路中得到的收益除以花费的时间。需要注意的是,一条没有任何交易的环路的盈利效率为0。你需要求

出所有消耗时间为正数的环路中,盈利效率最高的环路的盈利效率。答案向下取整保留到整数。如果没有任何一条

环路可以盈利,则输出0。

将如此之长的题面读完之后,你惊奇的发现,这题竟然是一道水题!

(虽然水但是我竟然发现我floyd和spfa都能写错我可能是OI之耻吧……)

那些乱七八糟的货物倒卖实际上可以总结为i~j,我倒卖的最大价值为w权,我经过的最短时间为t权,求sigma(w)/sigma(t)的最大值。

这明显是0/1分数规划套路,二分答案然后找正环就行了(不敢找负环怕爆ll……不知道可不可行。)

当然别忘了对于没法到达的(i,j),其不存在边,如果你用邻接矩阵的话,记的用什么方法判掉这些边。

(另外自己不能向自己倒卖商品)

#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=105;
const int K=1005;
const int INF=1e9;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int n,m,k;
int b[N][K],s[N][K],tim[N][N],cas[N][N],inq[N];
ll dis[N][N],big[N];
bool vis[N];
queue<int>q;
bool spfa(){
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++)big[i]=vis[i]=inq[i]=0;
    for(int i=1;i<=n;i++)q.push(i),vis[i]=inq[i]=1;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int v=1;v<=n;v++){
            if(big[v]-dis[u][v]<=big[u]){
                big[v]=big[u]+dis[u][v];
                if(!vis[v]){
                    inq[v]++;vis[v]=1;
                    if(inq[v]>n)return 1;
                    q.push(v);
                }
            }
        }
    }
    return 0;
}
inline bool pan(int w){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=(ll)cas[i][j]-(ll)w*tim[i][j];
    return spfa();
}
int erfen(int l,int r){
    while(l<r){
        int mid=(l+r+1)>>1;
        if(pan(mid))l=mid;
        else r=mid-1;
    }
    return l;
}
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++)
            tim[i][j]=INF,cas[i][j]=-INF;
        tim[i][i]=0;
    }
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        tim[u][v]=min(tim[u][v],w);
    }
    for(int l=1;l<=n;l++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(tim[i][j]-tim[i][l]>tim[l][j])
                    tim[i][j]=tim[i][l]+tim[l][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j&&tim[i][j]!=INF){
                cas[i][j]=0;
                for(int l=1;l<=k;l++)
                    if(b[i][l]>=0&&s[j][l]>=0&&b[i][l]<s[j][l])
                        cas[i][j]=max(cas[i][j],s[j][l]-b[i][l]);
            }
    printf("%d\n",erfen(0,INF));
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者:luyouqi233。               +

 +欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
2年前
8个在线接收手机短信验证码的免费网络服务整理
From:https://baijiahao.baidu.com/s?id1586819398136845808&wfrspider&forpc(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fbaijiahao.baidu.com%2Fs%3Fid%3D1586819398136
Stella981 Stella981
2年前
Jenkins的错误“error fetching remote repo origin”的问题解决
Jenkins的错误“errorfetchingremoterepoorigin”的问题解决参考文章:(1)Jenkins的错误“errorfetchingremoterepoorigin”的问题解决(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww
Stella981 Stella981
2年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Wesley13 Wesley13
2年前
P2P技术揭秘.P2P网络技术原理与典型系统开发
Modular.Java(2009.06)\.Craig.Walls.文字版.pdf:http://www.t00y.com/file/59501950(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fwww.t00y.com%2Ffile%2F59501950)\More.E
Wesley13 Wesley13
2年前
MySQL远程连接丢失问题解决方法(Lost connection to MySQL server)
MySQL远程连接丢失问题解决方法(LostconnectiontoMySQLserver)参考文章:(1)MySQL远程连接丢失问题解决方法(LostconnectiontoMySQLserver)(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww
Stella981 Stella981
2年前
Codeforces 848C Goodbye Souvenir [CDQ分治,二维数点]
洛谷(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.luogu.org%2Fproblemnew%2Fshow%2FCF848C)Codeforces(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fco
Stella981 Stella981
2年前
OSChina 周五乱弹 —— 我大便都是三角形的
Osc乱弹歌单(2020)请戳(这里(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fmusic.163.com%2F%23%2Fplaylist%3Fid%3D3170516388))【今日歌曲】@温家成(https://my.oschina.net/w
Stella981 Stella981
2年前
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法参考文章:(1)Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.codeprj.com%2Fblo
Stella981 Stella981
2年前
OpenYurt 入门
!头图.png(https://ucc.alicdn.com/pic/developerecology/d35db6f1020a4b85bf70f437903c342d.png)作者| 唐炳昌来源|阿里巴巴云原生公众号(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fmp.
Wesley13 Wesley13
2年前
BZOJ3168. [HEOI2013]钙铁锌硒维生素(线性代数+二分图匹配)
题目链接https://www.lydsy.com/JudgeOnline/problem.php?id3168(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.lydsy.com%2FJudgeOnline%2Fproblem.php%3Fid%3D3168)题解