传送门:[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;
}
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *