CCF CSP 202006-5 乔乔和牛牛逛超市

【题目描述】 乔乔和牛牛去逛超市了，超市里有 n 种商品，他们决定买一些商品回家。但是，第i 种商品一旦被选择，购买的个数就必须是 Li 和 Ri 之间的整数（含端点）。某些商品之间有依赖关系，依赖关系有两种：
• 1. 只有第 x 种商品被购买了，第 y 种商品才可以被购买。

• 2. 只有第 x 种商品被购买了，第 y 种商品的购买个数才可以恰好是 Lx 或 Rx 。

购买一个商品的带来的开心程度和这个商品购买的个数有关，若第 i 个商品购买了x 个 x > 0 ，则收益为 ai * x * x + bi * x + ci ，否则为 0 。

现在牛牛和乔乔想知道逛超市的最大总开心程度是多少，你能帮他们选购商品并确定购买商品数量吗？

【输入格式】
从标准输入读入数据。

第一行包含两个整数 n ，m ，表示商品数量和依赖关系数量。0 ≤ n ≤ 10^4,0 ≤ m ≤ 10^5。

接下来 n 行，每行包含五个整数 Li,Ri,ai,bi,ci ，描述一个商品。1 ≤ Li ≤ Ri ≤104,−5 ≤ a ≤ 5,−104 ≤ bi,ci ≤ 104, Li + 1 ≤ Ri − 1 。

接下来 m 行，每行包含三个整数 z, x,y ，表示第 x 种商品对第 y 种商品存在第 z种关系。1 ≤ x,y ≤ n,1 ≤ z ≤ 2。

【输出格式】
输出到标准输出。
输出一个整数，表示最大总开心程度。

image.png

【样例1 输出】

231

破题思路

1. 有一组商品，选择有依赖关系，每个点有一个权值。我们要选择任意多种使得权值最大，这个是一个最大权闭合子图模型。

2. 所谓闭合子图，就是在一个有向图中，我们选一组点集，使得这个点的集合，里的所有出边，都在这个点集内部。又称肥水不流外人田。
   因为一个点集不能有出边。我们要保证依赖关系。就是先选的要是被指的。比如选课，要先选语言课，完成了语言课的才能去选程设课。那么要从程设课向语言课指一条边。
   那么闭合子图的没有出边就能保证，不会有需要先选的没选，而选了又依赖的东西。

3. 本来每个物品就是一个点，这个点的权值，我们可以基于二次函数求范围内的最大值贪心到它的权值。但是这题有2种依赖关系，所以我们可以运用拆点的思想。每个物品我们拆成2种。一种是可以买但是不能买边界，另一种是在可以买的基础上还能买边界。

4. 所有买边界的要依赖于可以买的。也就是必须先选可以买，才能选买边界。

5. 针对可以买，我们要计算二次函数里【L+1, R-1】的最大值。 针对买边界就是二次函数取L还是取R的最大值。

6. 这2类点要求是互斥的，也就是说如果用了买边界，我们不能把买当中的第一类点的权值再算进去。所以我们构建第二类的点，需要用它的最大值减去第一类点的最大值。这样点集里包含第一类点代表买当中，如果2个都包含，代表买边界。

7. 余下的就是最大权闭合子图的模板了。所有源点向所有正权点建边。负权点向汇点建边。内部边的容量都为无穷大。随后跑DINIC算法求最大流等价于最小割。然后用所有正权点的和减去最小割的值就是答案。

8. 这道题写完提交直接就AC还是很爽的。大家加油！

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Main m = new Main();
        System.out.println(m.solve());
    }
    // 下面这组变量是DINIC跑最大流的基础变量。n是点数，m是边数
    int N = 20020, M = 300010, inf = (int) 1e9;
    // h e ne 3个数组 是数组模拟邻接表的建图方式，加边函数参加ADD
    // w 代表 残留网络的剩余容量。 d 是对所有点建立分层图，维护层数
    // cur 是当前层优化的数组 S代表源点 T代表汇点
    int[] h = new int[N], cur = new int[N], d = new int[N]; 
    int[] e = new int[M], ne = new int[M], w = new int[M];
    int S, T, idx = 0;
    
    int[][] goods;
    void add(int a, int b, int c) {
        e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
        e[idx] = a; w[idx] = 0; ne[idx] = h[b]; h[b] = idx++;
    }
    private long solve() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        goods = new int[n+1][];
        S = 0; T = 2 * n + 1;
        Arrays.fill(h, -1);
        
        long tot = 0; // 存所有正权点的和
        for (int i = 1; i <= n; i++) {
            goods[i] = new int[]{sc.nextInt(), sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt()};
            int v1 = cal(goods[i]), v2 = cal2(goods[i]) - v1;
            // i + n 是第二类点，i是第一类点
            add(i + n, i, inf);
            tot += Math.max(0, v1) + Math.max(0, v2);
            if (v1 > 0) add(S, i, v1);
            else if (v1 < 0) add(i, T, -v1);

            if (v2 > 0) add(S, i+n, v2);
            else if (v2 < 0) add(i+n, T, -v2);
        }

        for (int i = 0; i < m; i++) {
            int type = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt(), yy = y + n;
            if (type == 1) {
                add(y, x, inf);
            } else {
                add(yy, x, inf);
            }
        }
        
        // 正权和-最小割 为 最大闭合子图的解
        return tot - dinic();
    }

    // dinic 模板
    private long dinic() {
        long r = 0, flow;
        while (bfs()) while ((flow = find(S, inf)) != 0) r += flow;
        return r;
    }
    // dinic find 函数模板，带当前层优化
    private int find(int u, int limit) {
        if (u == T) return limit;
        int flow = 0;
        for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {
            int j = e[i];
            cur[u] = i;
            if (d[j] == d[u] + 1 && w[i] > 0) {
                int v = find(j, Math.min(w[i], limit - flow));
                if (v == 0) d[j] = -1;
                w[i] -= v; w[i ^ 1] += v; flow += v;
            }
        }
        return flow;
    }

    // dinic bfs 建分层图模板
    private boolean bfs() {
        Arrays.fill(d, -1);
        cur = h.clone();
        Queue<Integer> q = new LinkedList<>();
        q.offer(S); d[S] = 0;
        while (!q.isEmpty()) {
            int a = q.poll();
            for (int i = h[a]; i != -1; i = ne[i]) {
                int b = e[i];
                if (d[b] == -1 && w[i] > 0) {
                    d[b] = d[a] + 1;
                    if (b == T) return true;
                    q.offer(b);
                }
            }
        }
        return false;
    }

    // 二次函数求值
    int y(int a, int b, int c, int x) {
        return a * x * x + b * x + c;
    }
    // 第二类点求最大值
    private int cal2(int[] g) {
        return Math.max(y(g[2],g[3],g[4],g[0]), y(g[2],g[3],g[4],g[1]));
    }
    // 第一类点求最大值
    private int cal(int[] g) {
        int a = g[2], b = g[3], c = g[4], l = g[0], r = g[1];
        if (l + 1 > r - 1) return 0;
        if (a > 0) return Math.max(y(a,b,c,l+1), y(a,b,c,r-1));
        else if (a < 0) {
            double maxX = -b / 2.0 / a;
            if (maxX <= l) return y(a, b, c, l + 1);
            else if (maxX >= r) return y(a, b, c, r - 1);
            return Math.max(y(a, b, c, (int)Math.floor(maxX)), y(a, b, c, (int)Math.ceil(maxX)));
        }
        return y(a, b, c, b > 0 ? r - 1 : l + 1);
    }
}