[Codeforces Round #248][Codeforces 434D] Nanami's Power Plant

    题意：有n个点，设每个点的权值为$x_i$，要求$L_i<=x_i<=R_i$，另有m个约束$u_i,v_i,d_i$表示$x_{u_i}<=x_{v_i}+d$，求$\sum{f(i,x_i)}\ (f(i,x_i)=a_i x_i^2 + b_i x_i + c_i)$的最大值。($1<=n<=50,0<=m<=100,|a_i|<=10,|b_i|,|c_i|<=1000,|d_i|<=200$，且题目保证有解)

    题解：这种约束一般用网络流做，先直接讲一下建图方法。由于网络流求得是最小割，而我们要求最大值，所以可以先取一个足够大的M，使$M>=max\{f(i,x_i)\}$。

    1.将第i个点拆成$L_i-1...R_i$共$R_i-L_i+2$个点，记为$node(i,x)$。

    2.从S向$node(i,L_i-1)$连一条容量无穷大的边。

    3.从$node(i,R_i)$向T连一条容量无穷大的边。

    4.从$node(i,x)$向$node(i,x+1$连一条容量为$M-f(i,x+1)$的边，$L_i-1<=x<R_i$。

    5.从$node(u_i,x)$向$node(v_i,x-d)$连一条容量为无穷大的边，其中$L_{u_i}-1<=x<=R_{u_i},L_{v_i}-1<=x-d<=R_{v_i}$。

    第5次连边可以完成约束条件，这个从该图的最小割模型中很容易看出来。

    答案即$M*n-maxflow$。