【题解】[APIO2017] 商旅 分数规划 floyd luogu – 3778 —quhengyi11

传送门：[APIO2017] 商旅

题意：n 个点 m 条边的有向图，每条边的边权是你走过这条边消耗的时间，你要在上面跑来跑去，你有一个只能装一个物品的背包，现在知道每个点（集市）对于 k 种物品的买入和卖出价（假设没这种物品就为-1），求一条环路使得你的盈利效率最高，盈利效率的定义是 $\frac{总盈利}{消耗时间}$

数据范围:$1≤N≤100,1≤M≤9900,1≤K≤1000$

这道题一看就像分数规划（不知道的看这里分数规划入门），就是最优比率环的那种，但是刚开始想了半天却不知道怎么设边权 $QAQ$

其实不妨这样考虑，因为你的背包只能装一个物品，所以我们可以把任意两个点之间连一条边 $(u,v)$，价值为 $\forall k\in things\;max(s[v][k]-b[u][k])$，我们就求出了任意两点间的价值，任意两点间的距离可以由一遍 floyd 求出来。

由分数规划套路可知，我们要最大化 $\forall (u,v) \in Circle \;\frac{\sum w[u][v]}{\sum dis[u][v]}$($w$是价值，$dis$是距离)，即求出最小的 $k$满足：$$\exists Circle \;\frac{\sum w[u][v]}{\sum dis[u][v]}\leq k$$即：$$\exists Circle \;\sum w[u][v]-\sum dis[u][v]\times k\leq 0$$
整理一下：
$$\exists Circle \;\sum (w[u][v]-dis[u][v]\times k)\leq 0$$

我们设 $$e[u][v]=w[u][v]-dis[u][v]\times k$$

即我们要求的是 $$\exists Circle \;\sum (e[u][v])\leq 0$$

然后二分 k 然后用 SPFA 判负环即可

代码：

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define N 105
#define K 1005
#define inf 1073741823
#define int long long
int b[N][K], s[N][K], e[N][N], n, m, kk, x, y, w[N][N], l, r, wi;
int dis[N], cnt[K + 3], que[K + 3], hh, tt, g[N][N];
bool vis[N];
inline void add (int &x) {++x; if (x == K) x -= K;}
inline bool spfa (int s)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    fo (i, 1, n) fo (j, 1, n) g[i][j] = -w[i][j] + e[i][j] * wi;
    dis[s] = 0; hh = tt = 1; que[1] = s; cnt[s] = 0; vis[s] = 1;
    if (wi == 1)
        assert(wi);
    while (hh != tt + 1)
    {
        int u = que[hh];
        vis[u] = 0;
        add(hh);
        fo (v, 1, n)
            if (e[u][v] != inf && u != v && dis[v] >= dis[u] + g[u][v])
            {
                dis[v] = dis[u] + g[u][v];
                cnt[v] = cnt[u] + 1;
                if (cnt[v] > n) return 1;
                if (!vis[v])
                {
                    add(tt);
                    que[tt] = v;
                    vis[v] = 1;
                }
            }
    }
    return 0;
}
main ()
{
//  freopen("miao.txt", "r", stdin);
    scanf("%lld %lld %lld", &n, &m, &kk);
    fo (i, 1, n)
        fo (j, 1, kk)
            scanf("%lld %lld", &b[i][j], &s[i][j]);
    fo (i, 1, n) fo (j, 1, n) e[i][j] = inf; 
    fo (i, 1, n) e[i][i] = 0;
    fo (i, 1, m)
    {
        int DIS;
        scanf("%lld %lld %lld", &x, &y, &DIS);
        e[x][y] = DIS;
    }
    assert(e[x][y]);
    fo (k, 1, n)
        fo (i, 1, n)
            fo (j, 1, n)
                e[i][j] = std::min(e[i][j], e[i][k] + e[k][j]);
    fo (i, 1, n)
        fo (j, 1, n)
            fo (k, 1, kk)
                if (b[i][k] != -1 && s[j][k] != -1)
                    w[i][j] = std::max(w[i][j], s[j][k] - b[i][k]);
    l = 0; r = inf;
    while (l < r)
    {
        wi = (l + r + 1) >> 1;
        bool fl = 0;
        fo (i, 1, n)
            if (spfa(i))
                {fl = 1; break;}
        if (fl)
            l = wi;
        else
            r = wi - 1;
    }
    printf("%lld", l);
    return 0;
}