POJ3621或洛谷2868 [USACO07DEC]观光奶牛Sightseeing Cows

一道\(0/1\)分数规划+负环

POJ原题链接

洛谷原题链接

显然是\(0/1\)分数规划问题。
二分答案，设二分值为\(mid\)。
然后对二分进行判断，我们建立新图，没有点权，设当前有向边为\(z=(x,y)\)，\(time\)为原边权，\(fun\)为原点权，则将该边权换成\(mid\times time[z]+fun[x]\)，然后在上面跑\(SPFA\)。
如果有一个环使得\(\sum\{mid\times time[z]+fun[x]\}<0\)，则说明\(mid\)小了，而式子表示的意义就是原图存在负环；如果有环使得该式\(\geqslant0\)，那么说明答案不超过\(mid\)，这时\(SPFA\)就会正常结束。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
const int M = 5010;
int fi[N], di[M], ne[M], da[M], fun[N], q[N << 10], cnt[N], l, n;
bool v[N];
double dis[N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c<'0' || c>'9'; c = getchar())
        p |= c == '-';
    for (; c >= '0'&&c <= '9'; c = getchar())
        x = x * 10 + (c - '0');
    return p ? -x : x;
}
inline void add(int x, int y, int z)
{
    di[++l] = y;
    da[l] = z;
    ne[l] = fi[x];
    fi[x] = l;
}
bool judge(double mid)
{
    int head = 0, tail = 1, i, x, y;
    double z;
    bool p = 1;
    memset(dis, 66, sizeof(dis));
    memset(v, 0, sizeof(v));
    memset(cnt, 0, sizeof(cnt));
    dis[1] = 0;
    q[1] = 1;
    while (head != tail && p)
    {
        x = q[++head];
        v[x] = 0;
        for (i = fi[x]; i; i = ne[i])
        {
            y = di[i];
            z = mid * da[i] - fun[x];
            if (dis[y] > dis[x] + z)
            {
                dis[y] = dis[x] + z;
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= n)
                {
                    p = 0;
                    break;
                }
                if (!v[y])
                {
                    q[++tail] = y;
                    v[y] = 1;
                }
            }
        }
    }
    if (p)
        return false;
    return true;
}
int main()
{
    int i, m, x, y, z;
    double l = 0, r = 0, mid;
    n = re();
    m = re();
    for (i = 1; i <= n; i++)
        fun[i] = re();
    for (i = 1; i <= m; i++)
    {
        x = re();
        y = re();
        z = re();
        r += z;
        add(x, y, z);
    }
    r /= 2;
    while (l + 1e-3 < r)
    {
        mid = (l + r) / 2;
        if (judge(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.2f", l);
    return 0;
}

ps：因为我用的是\(VS\)，所以代码会自动补空格，而我本来的风格是没有空格的。

POJ3621或洛谷2868 [USACO07DEC]观光奶牛Sightseeing Cows

原文：https://www.cnblogs.com/Iowa-Battleship/p/9615123.html