题目大意:
给定一个长为n的序列，序列中的第i为上的值(x_i),序列第i位上的值(x_iin[l_i,r_i]),价值为(f_i(x_i)),其中(f_i(x) = a_ix^2 + b_ix + c_i),同时给出m个限制条件,每个限制条件用一个三元组(<u,v,d>)来表示,需要序列满足(x_u leq x_v + d)。求在满足所限制条件的情况下的(f_i(x_i))的最大和。
其中满足((1 leq n leq 50, 0 leq m leq 100 , -100 leq l_i leq r_i leq 100))
题目解答：
这道题跟[bzoj 3144 切糕]类似,由于网上关于切糕的题解已经烂大街了，在这里就不说了.
首先我们考虑在没有(x_i)的限制之下的答案计算：
直接取每段内的(max)不就好了嘛... ...
开一开脑洞，你就会构造出一个跟切糕差不多的层次模型
这不过这次是"最大割"而已
我们可以把所有有价值的边权全部都被所有值中的最大值减一下
这样我们直接求最小流再调整就行了。
而对于(X_u <= X_v + d)的限制
我们直接应用和切糕一样的思想来限制就可以了
一遍最大流即可
(ans = (max(f_i(x)) + 1)*n - maxflow)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 51;
const int maxm = 128;
const int maxnode = 25400;
const int maxedge = 254000;
const int inf = 0x3f3f3f3f;
struct Edge{
int to,next,cap;
}G[maxedge];
int head[maxnode],cnt=1;
void add(int u,int v,int c){
G[++cnt].to = v;
G[cnt].next = head[u];
G[cnt].cap = c;
head[u] = cnt;
}
inline void insert(int u,int v,int c){
add(u,v,c);add(v,u,0);
}
int dis[maxnode],q[maxnode],l,r;
int S,T;
#define v G[i].to
bool bfs(){
memset(dis,-1,sizeof dis);
dis[S] = 0;l = 0;r = -1;
q[++r] = S;
while(l <= r){
int u = q[l++];
for(int i = head[u];i;i=G[i].next){
if(dis[v] == -1 && G[i].cap){
dis[v] = dis[u] + 1;
q[++r] = v;
}
}
}return dis[T] != -1;
}int cur[maxnode];
int dfs(int u,int f){
if(u == T || f == 0) return f;
int ret = 0;
for(int &i = cur[u];i;i=G[i].next){
if(dis[v] == dis[u] + 1 && G[i].cap){
int x = dfs(v,cat_min(G[i].cap,f));
ret += x;f -= x;
G[i].cap -= x;G[i^1].cap += x;
if(f == 0) break;
}
}if(ret == 0) dis[u] = -1;
return ret;
}
inline int dinic(){
int ret = 0;
while(bfs()){
memcpy(cur,head,sizeof head);
ret += dfs(S,inf);
}return ret;
}
#undef v
int n;
inline int f(int x,int y){
y += 102;
return x*210+y;
}
int a[maxn],b[maxn],c[maxn],le[maxn],ri[maxn];
inline int calc(int i,int x){
return a[i]*x*x+b[i]*x+c[i];
}
int main(){
S = maxnode - 5;T = S+1;
read(n);int m;read(m);
int lim = -inf;
for(int i=1;i<=n;++i){
read(a[i]);read(b[i]);read(c[i]);
}
for(int i=1;i<=n;++i){
read(le[i]);read(ri[i]);
insert(S,f(i,le[i]-1),inf);
for(int j=le[i];j<=ri[i];++j){
lim = cat_max(lim,calc(i,j)+1);
}
insert(f(i,ri[i]),T,inf);
}
for(int i=1;i<=n;++i){
for(int j=le[i];j<=ri[i];++j){
insert(f(i,j-1),f(i,j),lim - calc(i,j));
}
}
for(int i=1,u,v,d;i<=m;++i){
read(u);read(v);read(d);
for(int j=le[u];j<=ri[u];++j){
if(j - d - 1 >= le[v] - 1 && j - d -1 <= ri[v])
insert(f(u,j-1),f(v,j-d-1),inf);
}
}
int ans = dinic();
printf("%d
",lim*n - ans);
getchar();getchar();
return 0;
}