摘要：
[CF434D]Nanami's Power Plant [CF434D]Nanami的PowerPlant主题的主要思想：二次函数、约束、表示。请最大化，其中是整数。对于的数据，请确保所有数字都是整数。总的来说，容量是。用于表示足够大的数字。对于每个二次函数中的所有连接边，容量为。
题目大意：
(N)个二次函数(f_i(x)=a_ix^2+b_ix+c_i(l_ile xle r_i))，(M)个约束条件((u,v,d))，表示(x_ule x_v+d)。请最大化(sum_{i=1}^nf_i(x_i))，其中(x_i)是整数。
对于(100\%)的数据，(1 leq N leq 50 , 0 leq M leq 100 , |a_i| leq 10 , |b_i| , |c_i| leq 1000 , −100 leq l_i leq r_i leq 100 , 1 leq u , v leq N , u eq v , |d| leq 200)，保证所有数均为整数。
思路：
将每个二次函数(i)拆成(node(i,l_i-1)sim node(i,r_i))共(r_i-l_i+2)个点。
对于所有的(node(i,l_i-1))，连边(s o node(i,l_i-1))，容量为(infty)。
对于所有的(node(i,r_i))，连边(s o node(i,r_i))，容量为(infty)。
用(lim)表示一个足够大的数，对于每个二次函数(i)中所有的(node(i,j))，连边(node(i,j-1) o node(i,j))，容量为(lim-f_i(j))。
考虑约束条件((u,v,d))，连边(node(u,j) o node(v,j−d))，容量为(infty)。
答案即为(lim imes n-maxflow)。
源代码：
#include<map>
#include<queue>
#include<cstdio>
#include<cctype>
#include<climits>
#include<cstring>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) neg|=ch=='-';
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return neg?-x:x;
}
const int N=51,V=1e4+1,E=1e5+1;
struct Edge {
int from,to,remain,next;
};
Edge e[E];
int h[V],sz,cnt;
inline void add_edge(const int &u,const int &v,const int &w) {
e[sz]=(Edge){u,v,w,h[u]};h[u]=sz++;
e[sz]=(Edge){v,u,0,h[v]};h[v]=sz++;
}
struct Func {
int a,b,c;
int operator () (const int &x) const {
return a*x*x+b*x+c;
}
};
Func f[N];
int l[N],r[N];
int lev[V],s,t,cur[V];
inline void bfs() {
memset(lev,-1,sizeof lev);
lev[s]=0;
std::queue<int> q;
q.push(s);
while(!q.empty()) {
const int &x=q.front();
for(register int i=h[x];~i;i=e[i].next) {
const int &y=e[i].to,&r=e[i].remain;
if(r&&!~lev[y]) {
lev[y]=lev[x]+1;
q.push(y);
}
}
q.pop();
}
}
int dfs(const int &x,const int &flow) {
if(x==t) return flow;
for(int &i=cur[x];~i;i=e[i].next) {
const int &y=e[i].to;
if(e[i].remain&&lev[y]>lev[x]) {
if(int d=dfs(y,std::min(flow,e[i].remain))) {
e[i].remain-=d;
e[i^1].remain+=d;
return d;
}
}
}
return 0;
}
inline int dinic() {
int maxflow=0;
for(;;) {
bfs();
if(!~lev[t]) break;
memcpy(cur,h,sizeof h);
while(int flow=dfs(s,INT_MAX)) {
maxflow+=flow;
}
}
return maxflow;
}
std::map<int,int> node[N];
int main() {
memset(h,-1,sizeof h);
const int n=getint(),m=getint();
for(register int i=1;i<=n;i++) {
const int a=getint(),b=getint(),c=getint();
f[i]=(Func){a,b,c};
}cnt=1;
s=cnt++;
for(register int i=1;i<=n;i++) {
l[i]=getint(),r[i]=getint();
for(register int j=l[i]-1;j<=r[i];j++) {
node[i][j]=cnt++;
}
}
const int M=INT_MAX/n;
for(register int i=1;i<=n;i++) {
add_edge(s,node[i][l[i]-1],INT_MAX);
for(register int j=l[i];j<=r[i];j++) {
add_edge(node[i][j-1],node[i][j],M-f[i](j));
}
add_edge(node[i][r[i]],t,INT_MAX);
}
for(register int i=0;i<m;i++) {
const int u=getint(),v=getint(),d=getint();
for(register int j=std::max(l[u],l[v]+d)-1;j<=std::min(r[u],r[v]+d);j++) {
add_edge(node[u][j],node[v][j-d],INT_MAX);
}
}
printf("%d
",M*n-dinic());
return 0;
}