# CodeForces 434D Nanami's Power Plant

Author: Fanyi Pu

Published: 2019-03-17

Canonical: <https://pufanyi.com/blog/oi-icpc/codeforces/cf434d>

CodeForces 434D Nanami's Power Plant 题解。

[原题链接](https://codeforces.com/problemset/problem/434/D)

有 $n$ 个二次函数，第 $i$ 个形如 $f_i(x)=a_ix^2+b_ix+c_i$

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

1. $x_i​$ 是 $[l_i,r_i]​$ 中的一个整数
2. 还给了 $m$ 条额外的限制，每条形如 `u v d`，表示的是 $x_u\leq x_v+d$

求最大的总收益。

$n\le 50; m\le 100; |a_i|\le 10;|b_i|,|c_i|\le1000;-100\le l_i\le r_i\le 100;|d_i|\le 200$。<sup>[1](https://pufanyi.com/blog/oi-icpc/codeforces/cf434d#user-content-fn-1)</sup>

## 题解

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

考虑网络流，对每个函数都建立 $[l_i,r_i]​$ 的点，点 $(i,j)​$ 表示函数 $f_i​$ 当 $x_i=j​$ 时的点。

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

我们从点 $(i,j)$ 向点 $(i,j+1)$（如果 $j=r_i$ 那就是超汇 $T$）流 $lim - f_i(j)$，从超源 $S$ 向点 $(i,l_i)$ 流 $\infty$。

大概就是这样一张图：

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

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

三条独立的函数链共享源点 S 和汇点 T。源点到每条链的起点容量为无穷大；从 (i,j) 出发的有限边容量为 lim 减 f\_i(j)。割掉这条边代表选择 x\_i 等于 j。点线省略中间的节点及边。

$\infty$

$c_1(l_1)$

$c_1(r_1)$

$c_2(l_2)$

$c_2(r_2)$

$c_3(l_3)$

$c_3(r_3)$

$S$

$T$

$(1,l_1)$

$(1,l_1+1)$

$(1,r_1)$

$(2,l_2)$

$(2,l_2+1)$

$(2,r_2)$

$(3,l_3)$

$(3,l_3+1)$

$(3,r_3)$

[View diagram in the original article](https://pufanyi.com/blog/oi-icpc/codeforces/cf434d)

链上的边 省略链段

记 $c_i(j)=lim-f_i(j)$。每条链割一条有限边，即选择对应的 $x_i=j$。点线省略中间节点及边。左右滑动查看完整图示

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

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

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

如果割绿色的那两条边：

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

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

尝试割掉 u 链的 (u,x+1) 到 (u,x+2) 和 v 链的 (v,x-d) 到 (v,x-d+1)。由 (u,x+1) 到 (v,x-d+1) 的无穷容量边可以绕过这两条割边，S 到 T 仍连通。两侧点线省略链的其余部分。

$\infty$

$S$

$T$

$(u,x)$

$(u,x+1)$

$(u,x+2)$

$(v,x-d)$

$(v,x-d+1)$

$(v,x-d+2)$

[View diagram in the original article](https://pufanyi.com/blog/oi-icpc/codeforces/cf434d)

链上的边 省略链段 约束边：$\infty$ *∕∕*&#x5C1D;试割掉的边 仍然连通的路径

绿色双斜杠对应 $x_u=x+1$、$x_v=x-d$，违反 $x_u\le x_v+d$。玫瑰色路径绕过两条割边，所以这不是一个 S–T 割。两侧点线省略链的其余部分。左右滑动查看完整图示

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

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

```plain
2 2
0 1 0
0 1 1
2 3
1 2
1 2 0
2 1 0
```

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

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

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

按文中的两函数反例建图。第一条链有 (1,2) 和 (1,3)，第二条链有 (2,1) 和 (2,2)。只有值为 2 的节点之间有双向无穷容量边。割掉 (1,3) 到 T 和 (2,2) 到 T，错误地允许 x₁=3、x₂=2。

$\infty$

$lim-2$

$lim-3$

$S$

$T$

$(1,2)$

$(1,3)$

$(2,1)$

$(2,2)$

[View diagram in the original article](https://pufanyi.com/blog/oi-icpc/codeforces/cf434d)

链上的边 约束边：$\infty$ *∕∕*&#x5C1D;试割掉的边

此时 $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\le x_2​$ 和 $x_2\le x_1​$ 可知 $x_1=x_2​$。

于是我们只得再建一个 $(i,r_i+1)$ 点，$(i,r_i)\to (i,r_i+1)$ 流 $lim-f_i(r_i)$，$(i,r_i+1)\to T$ 流 $\infty$。

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

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

新增 (1,4) 和 (2,3)，它们分别通过无穷容量边连接 T。新增 (1,3) 与 (2,3) 间的双向无穷容量边。合法最小割为 (1,2) 到 (1,3) 和 (2,2) 到 (2,3)，对应 x₁=x₂=2。

$\infty$

$lim-2$

$lim-3$

$S$

$T$

$(1,2)$

$(1,3)$

$(1,4)$

新增

$(2,1)$

$(2,2)$

$(2,3)$

[View diagram in the original article](https://pufanyi.com/blog/oi-icpc/codeforces/cf434d)

链上的边 约束边：$\infty$ *∕∕*&#x5C1D;试割掉的边

新增点 $(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;
}
```

## Footnotes

1. 翻译来自[luogu](https://www.luogu.org/problemnew/show/CF434D)，略有改动。