【题解】圈地游戏 01 分数规划 BZOJ – 3232

题目链接

首先二分答案 $mid$，设最终答案为 $ans$

假如当前 $mid \leq ans$，那么就有：

$$mid \leq \frac {\sum v _ i}{\sum c _ i}$$

也就是

$$\sum v _ i – mid \sum c _ i \geq 0$$

问题就变成了检测答案是否合法

这样建一个图：

以格线为边，格线交点为点

对于竖着的格线它的 $v$的数值就等于它左边所有的格子的价值之和

竖着的格线有两种方向：向上/向下

设定画圈的方向，比如是逆时针的话就让向上的格线 $v$为正，向下就 $v$为负

这样一上一下的话就等于前缀和做了一次差，相当于取了在同一行的两条竖着的格线之间的所有的格子

横着的格线它的 $v$就设为 $0$

格线的 $c$就设为它们原本的花费

在二分 check 的时候就把它的边权设为 $v – mid \times c$

再找是否存在正权环

若存在正权环则说明 $mid \leq ans$

否则说明 $mid > ans$

找正权环就用 SPFA

最好加个优化吧，比如双端队列，如果插入的元素比队首更优就直接插到队首

代码：

#include <bits/stdc++.h>

#define NS (3000)
#define MS (120000)
#define H(a, b) (((a) - 1) * (m + 1) + b)

using namespace std;

template<typename _Tp> inline void IN(_Tp &dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, N, sum[55][55];

struct graph
{
    int head[NS], nxt[MS], to[MS], x[MS], y[MS], sz;
    double w[MS];
    graph() { memset(head, -1, sizeof(head)), sz = 0; }
    void refresh(double z)
    {
        for (int i = 0; i < sz; i += 1) w[i] = y[i] - z * x[i];
    }
    void push(int a, int b, int c, int d)
    {
        nxt[sz] = head[a], to[sz] = b, x[sz] = c, y[sz] = d, head[a] = sz++;
    }
    int operator [] (const int a) const { return to[a]; }
} g;

double dis[NS];

bool book[NS];

int cnt[NS];

deque<int> que;

bool chk(double x)
{
    g.refresh(x), fill(dis + 1, dis + 1 + N, -1e9);
    memset(book + 1, 0, sizeof(bool) * N);
    memset(cnt + 1, 0, sizeof(int) * N);
    que.clear(), que.push_back(1);
    dis[1] = 0, cnt[1] = book[1] = 1;
    while (!que.empty())
    {
        int F = que[0]; que.pop_front(), book[F] = 0;
        for (int i = g.head[F]; ~i; i = g.nxt[i])
            if (dis[g[i]] < dis[F] + g.w[i])
            {
                dis[g[i]] = dis[F] + g.w[i];
                if (!book[g[i]])
                {
                    if (que.empty() || dis[g[i]] < dis[que[0]])
                        que.push_back(g[i]);
                    else que.push_front(g[i]);
                    book[g[i]] = 1;
                    if (++cnt[g[i]] >= N - 1) return 1;
                }
            }
    }
    return 0;
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), N = (n + 1) * (m + 1);
    for (int i = 1; i <= n; i += 1)
        for (int j = 1, a; j <= m; j += 1)
            IN(a), sum[i][j] = sum[i][j - 1] + a;
    for (int i = 1; i <= n + 1; i += 1)
        for (int j = 1, a; j <= m; j += 1)
        {
            IN(a);
            g.push(H(i, j), H(i, j + 1), a, 0);
            g.push(H(i, j + 1), H(i, j), a, 0);
        }
    for (int i = 1; i <= n; i += 1)
        for (int j = 1, a; j <= m + 1; j += 1)
        {
            IN(a);
            g.push(H(i, j), H(i + 1, j), a, -sum[i][j - 1]);
            g.push(H(i + 1, j), H(i, j), a, sum[i][j - 1]);
        }
    double l = 0, r = 1250, mid;
    while (r - l > 1e-5)
    {
        mid = (l + r) * 0.5;
        if (chk(mid)) l = mid;
        else r = mid;
    }
    printf("%.3f\n", l);
    return 0;
}