乔乔和牛牛逛超市

形式化题目

有 $n$ 种商品，每种可以不买，或买 $[L_i,R_i]$ 中的整数个。购买 $x$ 个时收益为 $a_ix^2+b_ix+c_i$ ，不买收益为 0。两类依赖关系：

只有 $x$ 被购买， $y$ 才可以被购买；
只有 $x$ 被购买， $y$ 的购买个数才可以恰好是 $L_y$ 或 $R_y$ 。

求满足依赖约束时的最大总收益。

思路

区间内购买数量的取值很多，但每个商品只需要保留三种最优选择：不买、买内部数量、买端点数量。

压缩为两种选择

端点收益为 $E=\max(f(L),f(R))$ ；内部收益 $I$ 只需检查内部区间端点和二次函数顶点附近的整数（开口向上时内部最小值，开口向下时在对称轴附近取最大）。

建闭合图

对商品 $i$ 建两个节点：

节点 $i$ 表示选择内部最优，权值 $I$ ；
节点 $i+n$ 表示把内部选择切换到端点，权值 $E-I$ ，并连强制边 $i+n\to i$ 。

于是不选两个节点表示不买，只选节点 $i$ 表示内部收益，同时选择两个节点表示端点收益。第一类依赖 $x$ 是 $y$ 的前置条件，连 $y\to x$ ；第二类依赖只在 $y$ 取端点时生效，连 $y+n\to x$ 。所有强制边容量为无穷大。

把正权点从源连入、负权点连向汇，最大权闭合子图的答案是正权和减最小割。

先看一个递归枚举全部购买数量的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，递归枚举每种商品的不买或所有合法购买数量。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

// 一条依赖关系：type 1 表示买 y 必须先买 x；type 2 表示 y 取端点数量时必须先买 x
struct Relation {
    int type, x, y;
};

int n, m;
int left_bound[MAXN], right_bound[MAXN], a[MAXN], b[MAXN], c[MAXN];
int amount[MAXN];                // amount[i] 表示第 i 种商品购买的个数，0 表示不买
long long best_answer = 0;
vector<Relation> relation;

// 第 i 种商品购买 x 个时的收益
long long get_value(int i, int x) {
    return 1LL * a[i] * x * x + 1LL * b[i] * x + c[i];
}

// 递归枚举每一种商品的选择：不买，或买 [left, right] 中的任意整数数量
void dfs(int position, long long value) {
    if (position > n) {
        // 所有商品选择完毕后，逐条检查依赖关系是否满足
        for (int i = 0; i < (int)relation.size(); i++) {
            Relation now = relation[i];
            if (now.type == 1 && amount[now.y] > 0 && amount[now.x] == 0) return;
            if (now.type == 2 && (amount[now.y] == left_bound[now.y] || amount[now.y] == right_bound[now.y])
                    && amount[now.x] == 0) return;
        }
        best_answer = max(best_answer, value);
        return;
    }
    amount[position] = 0;   // 这一层选择"不买"
    dfs(position + 1, value);
    for (int x = left_bound[position]; x <= right_bound[position]; x++) {
        amount[position] = x;
        dfs(position + 1, value + get_value(position, x));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> left_bound[i] >> right_bound[i] >> a[i] >> b[i] >> c[i];
    for (int i = 1; i <= m; i++) {
        Relation now;
        cin >> now.type >> now.x >> now.y;
        relation.push_back(now);
    }
    dfs(1, 0);
    cout << best_answer << '\n';

    return 0;
}

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXV = MAXN * 2 + 5;
const int MAXE = 500000;
const long long INF = (long long)4e18;

struct Edge {
    int to, next;
    long long flow;
};

int n, m, source, sink, edge_count = 1;
int head[MAXV], level[MAXV], current[MAXV];   // current 为当前弧优化指针
Edge edge[MAXE];

// 加一条 from -> to 容量为 flow 的边，并添加反向零容量边
void add_edge(int from, int to, long long flow) {
    edge[++edge_count] = {to, head[from], flow};
    head[from] = edge_count;
    edge[++edge_count] = {from, head[to], 0};
    head[to] = edge_count;
}

// BFS 分层，判断是否还有增广路
bool bfs() {
    queue<int> q;
    memset(level, -1, sizeof(level));
    level[source] = 0;
    q.push(source);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int i = head[node]; i; i = edge[i].next) {
            if (edge[i].flow > 0 && level[edge[i].to] == -1) {
                level[edge[i].to] = level[node] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return level[sink] != -1;
}

// DFS 沿分层图找增广路，limit 为当前允许通过的最大流量
long long dfs(int node, long long limit) {
    if (node == sink) return limit;
    for (int &i = current[node]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (edge[i].flow == 0 || level[to] != level[node] + 1) continue;
        long long pushed = dfs(to, min(limit, edge[i].flow));
        if (pushed) {
            edge[i].flow -= pushed;
            edge[i ^ 1].flow += pushed;
            return pushed;
        }
    }
    return 0;
}

// 最大流 = 最小割
long long dinic() {
    long long result = 0, pushed;
    while (bfs()) {
        memcpy(current, head, sizeof(head));
        while ((pushed = dfs(source, INF)) != 0) result += pushed;
    }
    return result;
}

// 二次收益函数 a*x^2 + b*x + c
long long get_value(int a, int b, int c, long long x) {
    return 1LL * a * x * x + 1LL * b * x + c;
}

// 求开区间 (left, right) 内部整数点上的最大收益，对应"内部数量"选择
long long get_inner_best(int left, int right, int a, int b, int c) {
    long long answer = -(long long)4e18;
    long long candidates[4];
    candidates[0] = left + 1;
    candidates[1] = right - 1;
    candidates[2] = left + 1;
    candidates[3] = right - 1;
    if (a < 0) {
        // 开口向下时对称轴附近收益最大，检查对称轴两侧整数
        long long denominator = -2LL * a;
        long long numerator = b;
        long long floor_value = numerator >= 0 ? numerator / denominator : -((-numerator + denominator - 1) / denominator);
        candidates[2] = floor_value;
        candidates[3] = floor_value + 1;
    }
    for (int i = 0; i < 4; i++) {
        // 把候选点裁剪回开区间内部
        long long x = max((long long)left + 1, min((long long)right - 1, candidates[i]));
        answer = max(answer, get_value(a, b, c, x));
    }
    return answer;
}

// 给节点加权：正权点从源连入并累加总正权，负权点连向汇
void add_weight(int node, long long value, long long &sum) {
    if (value > 0) {
        add_edge(source, node, value);
        sum += value;
    } else if (value < 0) {
        add_edge(node, sink, -value);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    source = 2 * n + 1;
    sink = source + 1;
    long long positive_sum = 0;

    // 每种商品建两个节点：i 表示内部收益，i+n 表示切换到端点收益
    for (int i = 1; i <= n; i++) {
        int left, right, a, b, c;
        cin >> left >> right >> a >> b >> c;
        long long endpoint = max(get_value(a, b, c, left), get_value(a, b, c, right));
        long long inner = get_inner_best(left, right, a, b, c);
        add_weight(i, inner, positive_sum);
        add_weight(i + n, endpoint - inner, positive_sum);
        add_edge(i + n, i, INF);   // 强制：选端点必须连带选内部
    }

    // 依赖关系转成闭合图强制边
    for (int i = 1; i <= m; i++) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) add_edge(y, x, INF);         // 买 y 必须先买 x
        else add_edge(y + n, x, INF);               // y 取端点时必须先买 x
    }

    // 最大权闭合子图答案 = 正权和 - 最小割
    cout << positive_sum - dinic() << '\n';

    return 0;
}

复杂度

图有 $O(n)$ 个点、 $O(n+m)$ 条边。二次函数最优值常数时间计算，Dinic 的复杂度满足本题规模，空间复杂度为 $O(n+m)$ 。

总结

区间内的二次收益先压缩为内部和端点两种选择；依赖条件再转为闭合图中的强制边。这样原问题成为标准最大权闭合子图。

子任务编号	分值	$n\le$	特殊性质
1	20	$10$	$R_i\le 5$
2	20	$10$	无
3	20	$10^4$	$z=1$
4	40	$10^4$	无