Codeforces 434(#248 Div1) D. Nanami's Power Plant

問題

整数x1, x2, ..., xnに対してn個の制約
l[i] ≦ xi ≦ r[i] (1≦i≦n)
および、m個の制約
x[u[i]] ≦ x[v[i]] + d[i] (1≦i≦m)が与えられるとき、
Σa[i] * x[i]^2 + b[i] * x[i] + c[i]を最大化せよ。

制約条件

n≦50, m≦100

ai

≦10,

bi

≦1000,

ci

≦1000

-100≦l[i]≦r[i]≦100

方針

以下f(i, x) = a[i]*x[i]^2 + b[i]*x[i] + c[i]と書く。

最小カット。
m個の制約がない場合を考える。
各変数ごとに、xi = kに相当する頂点を考えたい。
以後この頂点を(xi, k)とあらわす。

カットで考えたいので、(xi, k)がT側⇔xi≦kを意味するようにする。
すると、xi = kであるときにf(i, k)の得点が入るようにするためには、
(xi, k)と(xi, k - 1)の間を容量f(i, k)の辺でつないで、
切れたときにf(i, k)のカットが増えるようにすればよい。

（実際にはf(i, k)が負になりうるので、f(i, k) + BIGとして、後からBIGを全部引く）
また、xi = l[i]もありうるので、作る頂点は(xi, l[i] - 1)から(xi, r[i])まで。

Sから(xi, l[i] - 1)へは容量無限の辺
(xi, r[i])からTへは容量無限の辺を張る。

m個の制約を実現する方法を考える。
xu≦xv + dなる制約があるということは、
全てのkについてk

ソースコード

int n, m;
int a[50], b[50], c[50];
int l[50], r[50];

int f(int i, int x){
	return a[i] * x * x + b[i] * x + c[i];
}

int main(){
	
	cin >> n >> m;
	
	const ll BIG = 1000000;
	int s = 0, t;
	int base[60] = {};
	
	rep(i, n) cin >> a[i] >> b[i] >> c[i];
	rep(i, n){
		cin >> l[i] >> r[i];
		base[i] = s;
		s += r[i] - l[i] + 2;
	}
	t = s + 1;
	
	flowGraph g(t + 1);
	rep(i, n){
		g.add(s, base[i], inf);
		int k = base[i];
		rep(j, r[i] - l[i] + 1) g.add(k, k + 1, BIG - f(i, l[i] + j)), k++;
		g.add(k, t, inf);
	}
	rep(i, m){
		int u, v, d;
		cin >> u >> v >> d; u--; v--;
		for(int j = l[u] - 1; j <= r[u]; j++){
			
			if(j - d >= l[v] - 1 && j - d <= r[v])
			g.add(j - l[u] + 1 + base[u], j - d - l[v] + 1 + base[v], inf);
		}
	}
	cout << n * BIG - g.max_flow(s, t) << endl;
	
	return 0;
}