[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\)。

#include <bits/stdc++.h>
using namespace std;
const int maxn=10060,maxm=100010,inf=~0U>>2;

int head[maxn],nxt[maxm],E[maxm],F[maxm],Ecnt;
int ncnt[maxn];
int a[60],b[60],c[60];
int l[60],r[60];
int M;
int n,m,S,T;

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

int node(int x,int e)
{
	return ncnt[x]+e-l[x]+2;
}

void Add_Edge(int x,int y,int flow)
{
	nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;F[Ecnt]=0;
	nxt[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;F[Ecnt]=flow;
}

int h[maxn],cur[maxn],argu;
bool BFS()
{
	static int q[maxn];
	memset(h,0,sizeof(h));
	for (int i=1;i<=node(n,r[n]);i++) cur[i]=head[i];
	int top=0,tail=0;
	q[0]=S;
	h[S]=1;
	while (top<=tail)
	{
		int x=q[top++];
		for (int i=head[x];i;i=nxt[i]) if (!h[E[i]] && F[i^1])
			h[E[i]]=h[x]+1,q[++tail]=E[i];
	}
	return h[T]>0;
}

bool DFS(int x,int flow)
{
	if (x==T) {argu=flow;return 1;}
	for (int &i=cur[x];i;i=nxt[i]) if (h[E[i]]==h[x]+1 && F[i^1])
		if (DFS(E[i],min(flow,F[i^1])))
		{
			F[i]+=argu;
			F[i^1]-=argu;
			return true;
		}
	h[x]=0;
	return false;
}

int Dinic()
{
	int res=0;
	while (BFS()) while (DFS(S,inf)) res+=argu;
	return res;
}

int main()
{
	Ecnt=1;
	S=1;T=2;ncnt[1]=2;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for (int i=1;i<=n;i++)
		scanf("%d%d",&l[i],&r[i]),ncnt[i+1]=ncnt[i]+r[i]-l[i]+2;
	M=500000;
	for (int i=1;i<=n;i++)
	{
		Add_Edge(S,node(i,l[i]-1),inf);
		Add_Edge(node(i,r[i]),T,inf);
		for (int j=l[i];j<=r[i];j++)
			Add_Edge(node(i,j-1),node(i,j),M-f(i,j));
	}
	for (int i=1;i<=m;i++)
	{
		int u,v,d;
		scanf("%d%d%d",&u,&v,&d);
		for (int j=max(l[v]+d-1,l[u]-1);j<=min(r[v]+d,r[u]);j++)
			Add_Edge(node(u,j),node(v,j-d),inf);
	}
	int ans=Dinic();
	printf("%d\n",M*n-ans);
	return 0;
}