洛谷P3778 [APIO2017] 商旅题解

题目链接：P3778 [APIO2017] 商旅

题意：

在广阔的澳大利亚内陆地区长途跋涉后，你孤身一人带着一个背包来到了科巴。你被这个城市发达而美丽的市场所深深吸引，决定定居于此，做一个商人。科巴有\(N\)个集市，集市用从 \(1\) 到 \(N\) 的整数编号，集市之间通过 \(M\) 条单向道路连接，通过每条道路都需要消耗一定的时间。

在科巴的集市上，有 \(K\) 种不同的商品，商品用从 \(1\) 到 \(K\) 的整数编号。每个集市对每种商品都有自己的定价，买入和卖出商品的价格可以是不同的。并非每个集市都可以买卖所有的商品：一个集市可能只提供部分商品的双向交易服务；对于一种商品，一个集市也可能只收购而不卖出该商品或只卖出而不收购该商品。如果一个集市收购一种商品，它收购这种商品的数量是不限的，同样，一个集市如果卖出一种商品，则它卖出这种商品的数量也是不限的。

为了更快地获得收益，你决定寻找一条盈利效率最高的环路。环路是指带着空的背包从一个集市出发，沿着道路前进，经过若干个市场并最终回到出发点。在环路中，允许多次经过同一个集市或同一条道路。在经过集市时，你可以购买或者卖出商品，一旦你购买了一个商品，你需要把它装在背包里带走。由于你的背包非常小，任何时候你最多只能持有一个商品。在购买一个商品时，你不需要考虑你是否有足够的金钱，但在卖出时，需要注意只能卖出你拥有的商品。

从环路中得到的收益为在环路中卖出商品得到的金钱减去购买商品花费的金钱，而一条环路上消耗的时间则是依次通过环路上所有道路所需要花费的时间的总和。环路的盈利效率是指从环路中得到的收益除以花费的时间。需要注意的是，一条没有任何交易的环路的盈利效率为 \(0\) 。

你需要求出所有消耗时间为正数的环路中，盈利效率最高的环路的盈利效率。答案向下取整保留到整数。如果没有任何一条环路可以盈利，则输出 \(0\) 。

输入格式：

从标准输入中读取输入数据。

第一行包含 \(3\) 个正整数 \(N,M,K\) ，分别表示集市数量、道路数量和商品种类数量。

接下来的 \(N\) 行，第 \(i\) 行中包含 \(2K\) 个整数 \(B_{i,1},S_{i,1},B_{i,2},S_{i,2},\dots B_{i,K},S_{i,K}\) 描述一个集市。

对于任意的 \(1 \leq j \leq K\) ，整数 \(B_{i,j}\) 和 \(S_{i,j}\) 分别表示在编号为 \(i\) 的集市上购买、卖出编号为 \(j\) 的商品时的交易价格。如果一个交易价格为 \(-1\) ，则表示这个商品在这个集市上不能进行这种交易。

接下来 \(M\) 行，第 \(p\) 行包含 \(3\) 个整数 \(V_p,W_p,T_p\) ，表示存在一条从编号为 \(V_p\) 的市场出发前往编号为 \(W_p\) 的市场的路径花费 \(T_p\) 分钟。

输出格式：

输出到标准输出中。

输出包含一个整数，表示盈利效率最高的环路盈利效率，答案向下取整保留到整数。如果没有任何一条环路可以盈利，则输出 \(0\) 。

数据范围：

\(1 \leq N \leq 100,~1 \leq M \leq 9900,~1 \leq K \leq 1000\)

如果在编号为 \(i (1 \leq i \leq N)\) 的集市中，编号为 \(j (1 \leq j \leq K)\) 的商品既可以购买又可以卖出，则\(0 \leq S_{i,j} \leq B_{i,j} \leq 10^9\)。

对于编号为 \(p (1 \leq p \leq M)\) 的道路，保证 \(V_p \not= W_p\) 且 \(1 \leq T_p \leq 10^7\) 。

不存在满足 \(1 \leq p < q \leq M\) 的 \(p,q\) 使得 \((V_p, W_p)=(V_q, W_q)\) 。

数据范围挺复杂的，其实就是说无重边无自环，~~而且那个S和B的限制其实就是防止你卡bug刷分~~

注意到答案是个比值的最小值，因此考虑 \(01\) 分数规划，则 \[ \textstyle\frac{A}{B} \ge x \Rightarrow A - xB \ge 0 \] 其中 \(A\) 表示某个简单环得到的最大价值，\(B\) 表示相应的时间，\(x\) 是二分的值。

为什么是简单环呢？其实分析一下可以发现走回路一定不会更优，~~证明略~~。

有一种做法是把一个点看作 \(n\) 个点（ \(n\) 为物品种数），然后判个正环啥的，但是复杂度不太行。

注意到这道题最麻烦的其实是 \(A\) 的计算，因此我们从决策的角度分析其性质。

考虑更好的做法。注意到买了一个物品之后，肯定是买了以后扛着它跑一段路再卖掉。

形式化地，我们可以把链 \(u \leadsto v\) 看作一个整体，计算 \(u\) 买入 \(v\) 卖出的最大收益。

显然他们走的路一定是最短路，因此可以 \(\mathtt{Floyd}\) 预处理出所有的 \(\mathtt{dis}(u,v)\) 。

记 \(g_{i,j}\) 为 \(i\leadsto j\) 的最大收益。显然 \(\displaystyle g_{i,j} = \max_{1\le k \le n}\{s_{j,k}-b_{i,k}\}\) （\(-1\) 啥的除外）。

接下来就是赋新边权判正环了。或者说应该叫非负环。

显然可以用 \(\mathtt{SPFA}\) ，但比较麻烦，并且要特判一下零环，即枚举 \(u,v\) 看 \(w(u,v)+d_u\) 是否等于 \(d_v\) 。

其实有更简单的做法。具体地，设 \(f_{i,j} = g_{i,j} - x\times \mathtt{dis}(i,j)\) 。特别地， \(f_{i,i} = -\infty\) ，然后跑 \(\mathtt{Floyd}\) 转移。 \[ f_{i,j} \uparrow \max_{1 \le k \le |V|}\{f_{i,k}+f_{k,j}\} \] 这样最后算出来的 \(f_{i,i}\) 就是以 \(i\) 为起点的最大环，只要看看是不是非负就好了。

这里因为向下取整，所以可以直接用整数的二分，不过要注意一下取整方向和能否取等之类的。

这道题里由于算的是 \(\left\lfloor \frac{A}{B} \right\rfloor \ge x\) ，不难发现它正好等价于 \(\left\lfloor A-xB \right\rfloor \ge 0\) ，所以直接二分即可。

时间复杂度 \(\mathcal{O}(|V|^3 \log M)\) ，其中 \(M=g_{\max}\) 为值域。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(105))
#define K ((int)(1e3+15))

int V,E,n,b[N][K],s[N][K],d[N][N],f[N][N],g[N][N];
void Floyd()
{
    for(int i=1; i<=V; i++)
        for(int j=1; j<=V; j++) d[i][j] = INF;

    for(int i=1,u,v,w; i<=E; i++)
    { cin >> u >> v >> w; down(d[u][v],w); }
    
    for(int k=1; k<=V; k++)
        for(int i=1; i<=V; i++)
            for(int j=1; j<=V; j++) down(d[i][j], d[i][k] + d[k][j]);
}
bool test(int x)
{
    for(int i=1; i<=V; i++)
        for(int j=1; j<=V; j++)
            f[i][j] = (i==j) ? -INF : (g[i][j] - x * d[i][j]);
    for(int k=1; k<=V; k++)
        for(int i=1; i<=V; i++)
            for(int j=1; j<=V; j++) up(f[i][j], f[i][k] + f[k][j]);

    int res = -INF;
    for(int i=1; i<=V; i++) up(res, f[i][i]);
    return res >= 0;
}
int solve(int l,int r)
{
    for(int mid; l < r; )
    {
        mid = (l + r + 1) >> 1;
        test(mid) ? (l = mid) : (r = mid-1);
    }
    return l;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> V >> E >> n; int tmp = 0;
    for(int i=1; i<=V; i++)
        for(int j=1; j<=n; 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<=V; i++)
        for(int j=1; j<=V; up(tmp, g[i][j++]))
            for(int k=1; k<=n; k++) up(g[i][j], s[j][k] - b[i][k]);
    Floyd(); cout << solve(0, tmp) << '\n';
    return 0;
}