题目地址：洛谷：【P3778】[APIO2017]商旅 – 洛谷、BZOJ：Problem 4898. — [Apio2017]商旅

题目描述

在广阔的澳大利亚内陆地区长途跋涉后，你孤身一人带着一个背包来到了科巴。你被这个城市发达而美丽的市场所深深吸引，决定定居于此，做一个商人。科巴有个集市，集市用从1到N的整数编号，集市之间通过M条单向道路连接，通过每条道路都需要消耗一定的时间。
在科巴的集市上，有K种不同的商品，商品用从1到K的整数编号。每个集市对每种商品都有自己的定价，买入和卖出商品的价格可以是不同的。并非每个集市都可以买卖所有的商品：一个集市可能只提供部分商品的双向交易服务；对于一种商品，一个集市也可能只收购而不卖出该商品或只卖出而不收购该商品。如果一个集市收购一种商品，它收购这种商品的数量是不限的，同样，一个集市如果卖出一种商品，则它卖出这种商品的数量也是不限的。
为了更快地获得收益，你决定寻找一条盈利效率最高的环路。环路是指带着空的背包从一个集市出发，沿着道路前进，经过若干个市场并最终回到出发点。在环路中，允许多次经过同一个集市或同一条道路。在经过集市时，你可以购买或者卖出商品，一旦你购买了一个商品，你需要把它装在背包里带走。由于你的背包非常小，任何时候你最多只能持有一个商品。在购买一个商品时，你不需要考虑你是否有足够的金钱，但在卖出时，需要注意只能卖出你拥有的商品。
从环路中得到的收益为在环路中卖出商品得到的金钱减去购买商品花费的金钱，而一条环路上消耗的时间则是依次通过环路上所有道路所需要花费的时间的总和。环路的盈利效率是指从环路中得到的收益除以花费的时间。需要注意的是，一条没有任何交易的环路的盈利效率为0。
你需要求出所有消耗时间为正数的环路中，盈利效率最高的环路的盈利效率。答案向下取整保留到整数。如果没有任何一条环路可以盈利，则输出0。

输入输出格式

输入格式：
从标准输入中读取输入数据。
第一行包含3个正整数，N、M和K，分别表示集市数量、道路数量和商品种类数量。
接下来的N行，第i行中包含2K个整数Bi,1, Si,1, Bi,2, Si,2, …, Bi,K, Si,K描述一个集市。对于任意的1≤j≤K, 整数Bi,j和Si,j分别表示在编号为i的集市上购买、卖出编号为j的商品时的交易价格。如果一个交易价格为-1，则表示这个商品在这个集市上不能进行这种交易。
接下来M行，第p行包含3个整数,Vp、Wp和Tp, 表示存在一条从编号为Vp的市场出发前往编号为Wp的市场的路径花费Tp分钟。

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

输入输出样例

输入样例#1：

4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

输出样例#1：

2

说明

1≤N≤100，1≤M≤9900，1≤K≤1000。

题解

参考资料：商旅 – APIO2017-商旅题解.pdf
分数规划的模型。
考虑二分答案，对于一个二分出来的答案ans，判断是否存在环路使得效率≥ans，也就是下面的式子
\displaystyle \frac{\sum profit}{\sum time} \geq ans
转换成
\displaystyle \sum profit - ans \cdot \sum time \geq 0
考虑对任意点对(i, j)连边，权值为i买入j卖出商品的最大收益减去两点间最短路的ans倍。对这个图找是否存在正环就可以判断二分的答案是否可行。
我们需要预处理i买入j卖出商品的最大收益，枚举i和j和商品即可；预处理最短路，采用Floyd即可。预处理的总复杂度是O(N^2K+N^3)的。
每一次check，需要构建新图，Floyd判正环，考虑边权取反后判负环，就是一个最短路的常规写法。每一次check的复杂度是O(N^3)的。
因此这个算法的总复杂度是O(N^3 \log N)的。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 105, MAXK = 1005;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, m, K;

LL gra[MAXN][MAXN], prof[MAXN][MAXN], b[MAXN][MAXK], s[MAXN][MAXK];
LL dis[MAXN][MAXN];

inline bool check(LL mid) {
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(gra[i][j] == INF) continue;
            dis[i][j] = std::min(INF, gra[i][j] * mid - prof[i][j]);
        }
        dis[i][i] = INF;
    }
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                dis[i][j] = std::min(INF, std::min(dis[i][j], dis[i][k] + dis[k][j]));
            }
            if(dis[i][i] <= 0) return true;
        }
    }
    return false;
}

int u, v;
LL w;

int main() {
    memset(gra, 0x3f, sizeof(gra));
    n = readint(); m = readint(); K = readint();
    for(int i = 1; i <= n; i++) {
        gra[i][i] = 0;
        for(int j = 1; j <= K; j++) {
            b[i][j] = readint(); s[i][j] = readint();
        }
    }
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint(); w = readint();
        gra[u][v] = std::min(gra[u][v], w);
    }
    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) continue;
                prof[i][j] = std::max(prof[i][j], s[j][k] - b[i][k]);
            }
        }
    }
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                gra[i][j] = std::min(gra[i][j], gra[i][k] + gra[k][j]);
            }
        }
    }
    LL l = 0, r = 1e15, mid;
    while(r - l > 1) {
        mid = (l + r) >> 1;
        if(check(mid)) l = mid; else r = mid;
    }
    printf("%lld", l);
    return 0;
}