CodeForces 434D Nanami's Power Plant

2019-03-17

原题链接

有 \(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\)。1

题解

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

考虑网络流，对每个函数都建立 \([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)\)
\(\infty\)
\(c_2(l_2)\)
\(c_2(r_2)\)
\(\infty\)
\(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)\)
记 \(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\)
\(\infty\)
\(\infty\)
\(S\)
\(T\)
\((u,x)\)
\((u,x+1)\)
\((u,x+2)\)
\((v,x-d)\)
\((v,x-d+1)\)
\((v,x-d+2)\)
绿色双斜杠对应 \(x_u=x+1\)、\(x_v=x-d\)，违反 \(x_u\le x_v+d\)。玫瑰色路径绕过两条割边，所以这不是一个 S–T 割。两侧点线省略链的其余部分。左右滑动查看完整图示

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

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

code
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\)
\(\infty\)
\(lim-2\)
\(lim-3\)
\(\infty\)
\(\infty\)
\(S\)
\(T\)
\((1,2)\)
\((1,3)\)
\((2,1)\)
\((2,2)\)
此时 \(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\)
\(\infty\)
\(\infty\)
\(lim-2\)
\(lim-3\)
\(\infty\)
\(\infty\)
\(\infty\)
\(\infty\)
\(\infty\)
\(S\)
\(T\)
\((1,2)\)
\((1,3)\)
\((1,4)\)
新增
\((2,1)\)
\((2,2)\)
\((2,3)\)
新增
新增点 \((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，略有改动。 ↩

Cite this post

@misc{pu2019cf434d,
  author = {Pu, Fanyi},
  title  = {CodeForces 434D Nanami's Power Plant},
  year   = {2019},
  month  = {3},
  url    = {https://pufanyi.com/blog/cf434d}
}