【題目描述】 喬喬和牛牛去逛超市了贸铜，超市里有 n 種商品聪廉，他們決定買一些商品回家。但是酥馍，第i 種商品一旦被選擇辩昆，購買的個(gè)數(shù)就必須是 Li 和 Ri 之間的整數(shù)（含端點(diǎn)）。某些商品之間有依賴關(guān)系旨袒，依賴關(guān)系有兩種：
? 1. 只有第 x 種商品被購買了汁针，第 y 種商品才可以被購買。
? 2. 只有第 x 種商品被購買了砚尽，第 y 種商品的購買個(gè)數(shù)才可以恰好是 Lx 或 Rx 施无。
購買一個(gè)商品的帶來的開心程度和這個(gè)商品購買的個(gè)數(shù)有關(guān)，若第 i 個(gè)商品購買了x 個(gè) x > 0 必孤，則收益為 ai * x * x + bi * x + ci 猾骡，否則為 0 。
現(xiàn)在牛牛和喬喬想知道逛超市的最大總開心程度是多少敷搪，你能幫他們選購商品并確定購買商品數(shù)量嗎兴想？
【輸入格式】
從標(biāo)準(zhǔn)輸入讀入數(shù)據(jù)。
第一行包含兩個(gè)整數(shù) n 赡勘，m 嫂便，表示商品數(shù)量和依賴關(guān)系數(shù)量。0 ≤ n ≤ 10^4,0 ≤ m ≤ 10^5闸与。
接下來 n 行顽悼，每行包含五個(gè)整數(shù) Li,Ri,ai,bi,ci ，描述一個(gè)商品几迄。1 ≤ Li ≤ Ri ≤104,?5 ≤ a ≤ 5,?104 ≤ bi,ci ≤ 104, Li + 1 ≤ Ri ? 1 蔚龙。
接下來 m 行，每行包含三個(gè)整數(shù) z, x,y 映胁，表示第 x 種商品對(duì)第 y 種商品存在第 z種關(guān)系木羹。1 ≤ x,y ≤ n,1 ≤ z ≤ 2。
【輸出格式】
輸出到標(biāo)準(zhǔn)輸出。
輸出一個(gè)整數(shù)坑填，表示最大總開心程度抛人。
【樣例1 輸出】
231
破題思路
有一組商品，選擇有依賴關(guān)系脐瑰，每個(gè)點(diǎn)有一個(gè)權(quán)值妖枚。我們要選擇任意多種使得權(quán)值最大，這個(gè)是一個(gè)最大權(quán)閉合子圖模型苍在。
所謂閉合子圖绝页，就是在一個(gè)有向圖中，我們選一組點(diǎn)集寂恬，使得這個(gè)點(diǎn)的集合续誉，里的所有出邊，都在這個(gè)點(diǎn)集內(nèi)部初肉。又稱肥水不流外人田酷鸦。
因?yàn)橐粋€(gè)點(diǎn)集不能有出邊。我們要保證依賴關(guān)系牙咏。就是先選的要是被指的臼隔。比如選課，要先選語言課妄壶，完成了語言課的才能去選程設(shè)課躬翁。那么要從程設(shè)課向語言課指一條邊。
那么閉合子圖的沒有出邊就能保證盯拱，不會(huì)有需要先選的沒選盒发，而選了又依賴的東西。本來每個(gè)物品就是一個(gè)點(diǎn)狡逢，這個(gè)點(diǎn)的權(quán)值宁舰，我們可以基于二次函數(shù)求范圍內(nèi)的最大值貪心到它的權(quán)值。但是這題有2種依賴關(guān)系奢浑，所以我們可以運(yùn)用拆點(diǎn)的思想蛮艰。每個(gè)物品我們拆成2種。一種是可以買但是不能買邊界雀彼，另一種是在可以買的基礎(chǔ)上還能買邊界壤蚜。
所有買邊界的要依賴于可以買的。也就是必須先選可以買徊哑，才能選買邊界袜刷。
針對(duì)可以買，我們要計(jì)算二次函數(shù)里【L+1, R-1】的最大值莺丑。 針對(duì)買邊界就是二次函數(shù)取L還是取R的最大值著蟹。
這2類點(diǎn)要求是互斥的墩蔓，也就是說如果用了買邊界，我們不能把買當(dāng)中的第一類點(diǎn)的權(quán)值再算進(jìn)去萧豆。所以我們構(gòu)建第二類的點(diǎn)奸披，需要用它的最大值減去第一類點(diǎn)的最大值。這樣點(diǎn)集里包含第一類點(diǎn)代表買當(dāng)中涮雷，如果2個(gè)都包含阵面，代表買邊界。
余下的就是最大權(quán)閉合子圖的模板了洪鸭。所有源點(diǎn)向所有正權(quán)點(diǎn)建邊样刷。負(fù)權(quán)點(diǎn)向匯點(diǎn)建邊。內(nèi)部邊的容量都為無窮大卿嘲。隨后跑DINIC算法求最大流等價(jià)于最小割颂斜。然后用所有正權(quán)點(diǎn)的和減去最小割的值就是答案夫壁。
這道題寫完提交直接就AC還是很爽的拾枣。大家加油！
import java.util.*;
public class Main {
public static void main(String[] args) {
Main m = new Main();
System.out.println(m.solve());
}
// 下面這組變量是DINIC跑最大流的基礎(chǔ)變量盒让。n是點(diǎn)數(shù)梅肤，m是邊數(shù)
int N = 20020, M = 300010, inf = (int) 1e9;
// h e ne 3個(gè)數(shù)組 是數(shù)組模擬鄰接表的建圖方式，加邊函數(shù)參加ADD
// w 代表 殘留網(wǎng)絡(luò)的剩余容量邑茄。 d 是對(duì)所有點(diǎn)建立分層圖姨蝴，維護(hù)層數(shù)
// cur 是當(dāng)前層優(yōu)化的數(shù)組 S代表源點(diǎn) T代表匯點(diǎn)
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; // 存所有正權(quán)點(diǎn)的和
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 是第二類點(diǎn)，i是第一類點(diǎn)
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);
}
}
// 正權(quán)和-最小割 為 最大閉合子圖的解
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 函數(shù)模板肺缕，帶當(dāng)前層優(yōu)化
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;
}
// 二次函數(shù)求值
int y(int a, int b, int c, int x) {
return a * x * x + b * x + c;
}
// 第二類點(diǎn)求最大值
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]));
}
// 第一類點(diǎn)求最大值
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);
}
}
