CodeForces 434D Nanami's Power Plant

有 $n$ 个二次函数，第 $i$ 个形如 $f_{i} (x) = a_{i} x^{2} + b_{i} x + c_{i}$

你的总收益是 $\sum_{i = 1}^{n} f_{i} (x_{i})$ ，但是有几个限制：

$x_{i} $ 是 $[l_{i}, r_{i}] $ 中的一个整数
还给了 $m$ 条额外的限制，每条形如 u v d，表示的是 $x_{u} \leq x_{v} + d$

求最大的总收益。

$n \leq 50; m \leq 100; | a_{i} | \leq 10; | b_{i} |, | c_{i} | \leq 1000; - 100 \leq l_{i} \leq r_{i} \leq 100; | d_{i} | \leq 200$ 。¹

题解

感觉和刚刚做过一场模拟赛的一道题很类似……

考虑网络流，对每个函数都建立 $[l_{i}, r_{i}] $ 的点，点 $(i, j) $ 表示函数 $f_{i} $ 当 $x_{i} = j $ 时的点。

我们考虑最小损失。设一个极大值 $l i m$ （大于所有的 $f_{i} (x)$ ），将也就是要求 $l i m - f_{i} (x)$ 的最小值。

我们从点 $(i, j)$ 向点 $(i, j + 1)$ （如果 $j = r_{i}$ 那就是超汇 $T$ ）流 $l i m - f_{i} (j)$ ，从超源 $S$ 向点 $(i, l_{i})$ 流 $\infty$ 。

大概就是这样一张图：

每个函数对应一条从 S 到 T 的链

记

c_i(j)=lim-f_i(j)

。每条链割一条有限边，即选择对应的

x_i=j

。点线省略中间节点及边。左右滑动查看完整图示

如果这些函数的取值互不干涉，那么 $n \times l i m - 最小割$ 就是答案。

我们考虑如何加入这些限制。

如果现在有限制 $x_{u} \leq x_{v} + d$ ，也就是 $x_{v} \geq x_{u} - d$ 。如果我们割了 $x_{u}$ 这条边，在 $v$ 这条链上我们只能割 $x_{u} - d$ 以后的边。那就不妨从 $u$ 这条表上所有的 $x$ 向 $v$ 这条边上所有的 $x - d$ 连一条 $\infty $ 的边。

如果割绿色的那两条边：

违反限制时，两条割边之间仍有旁路

绿色双斜杠对应

x_u=x+1

、

x_v=x-d

，违反

x_u\le x_v+d

。玫瑰色路径绕过两条割边，所以这不是一个 S–T 割。两侧点线省略链的其余部分。左右滑动查看完整图示

很开心地测一下样例，炸了……

我们来看这种情形（对样例 1 略有改动）：

code

建出来的图大概是长这样的：

补点前：两条链可以选出不相等的值

此时

x_1=3

、

x_2=2

，收益为

3+(2+1)=6

。但限制要求

x_1=x_2

；缺少

(2,3)

，就无法阻止这个非法选择。左右滑动查看完整图示

最小割是选 $(1, 3) \to T$ 和 $(2, 2) \to T$ 。

但显然 $(1, 3) \to T $ 是不能选的。因为由 $x_{1} \leq x_{2} $ 和 $x_{2} \leq x_{1} $ 可知 $x_{1} = x_{2} $ 。

于是我们只得再建一个 $(i, r_{i} + 1)$ 点， $(i, r_{i}) \to (i, r_{i} + 1)$ 流 $l i m - f_{i} (r_{i})$ ， $(i, r_{i} + 1) \to T$ 流 $\infty$ 。

补点后：约束延伸到区间右端点之外

新增点

(i,r_i+1)

以

\infty

连向 T。此时只有

x_1=x_2=2

合法，最小割为

(lim-2)+(lim-3)

，最大收益为

5

。左右滑动查看完整图示

这样就完美了。

cpp

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const LL maxn = 10005;
const LL maxm = 5000005;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const LL lim = 1000000000000;

struct Edge
{
    LL to, nxt, cap;
} e[maxm << 1];

LL first[maxn], first_bak[maxn];

inline void add_edge(LL from, LL to, LL cap)
{
    static LL cnt = -1;
    e[++cnt].nxt = first[from];
    first[from] = cnt;
    e[cnt].to = to;
    e[cnt].cap = cap;
    e[++cnt].nxt = first[to];
    first[to] = cnt;
    e[cnt].to = from;
    e[cnt].cap = 0;
}

LL n, m, S, T;

LL bh[105][205];
LL a[maxn], b[maxn], c[maxn];
LL ll[maxn];
LL rr[maxn];
LL dep[maxn];

inline LL getans(LL I, LL x)
{
    return a[I] * x * x + b[I] * x + c[I];
}

inline bool bfs()
{
    memset(dep, 0x3f, sizeof(dep));
    queue<LL> q;
    q.push(S);
    dep[S] = 0;
    for(int i = S; i <= T; ++i)
        first[i] = first_bak[i];
    while(!q.empty())
    {
        LL now = q.front();
        q.pop();
        for(int i = first[now]; ~i; i = e[i].nxt)
        {
            LL to = e[i].to;
            if(dep[to] >= inf && e[i].cap > 0)
            {
                dep[to] = dep[now] + 1;
                q.push(to);
            }
        }
    }
    return dep[T] < inf;
}

inline LL dfs(LL now, LL lim)
{
    if(!lim || now == T)
        return lim;
    LL flow = 0;
    for(int i = first[now]; ~i; i = e[i].nxt)
    {
        first[now] = i;
        register LL to = e[i].to, f;
        if(dep[to] == dep[now] + 1 && (f = dfs(to, min(lim, e[i].cap))) > 0)
        {
            lim -= f;
            flow += f;
            e[i].cap -= f;
            e[i ^ 1].cap += f;
            if(lim <= 0)
                break;
        }
    }
    return flow;
}

inline LL dinic()
{
    LL flow = 0;
    while(bfs())
        flow += dfs(S, inf);
    return flow;
}

int main()
{
    memset(first, 0xff, sizeof(first));
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; ++i)
        scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lld%lld", &ll[i], &rr[i]);
        add_edge(S, T + 1, inf);
        for(LL j = ll[i] + 100; j <= rr[i] + 101; ++j)
        {
            bh[i][j] = ++T;
            if(j != ll[i] + 100)
                add_edge(bh[i][j - 1], bh[i][j], lim - getans(i, j - 1 - 100));
        }
    }
    T++;
    for(LL i = 1; i <= n; ++i)
        add_edge(bh[i][rr[i] + 101], T, inf);
    for(int i = 1, u, v, d; i <= m; ++i)
    {
        scanf("%d%d%d", &u, &v, &d);
        for(int j = ll[u]; j <= rr[u] + 1; ++j)
            if(ll[v] <= j - d && j - d <= rr[v] + 1)
                add_edge(bh[u][j + 100], bh[v][j - d + 100], inf);
    }
    for(int i = S; i <= T; ++i)
        first_bak[i] = first[i];
    printf("%lld\n", n * lim - dinic());
    return 0;
}

翻译来自luogu，略有改动。 ↩

题解

Footnotes

Cite this post