题目
题解
先考虑假设球队$A$已经胜了$x$场，一共要打$y$场，则能产生的代价为$C_Ax^2+D_A(y-x)^2=(C_A+D_A)x^2+D_Ay^2-2D_Ax$
计算多胜一场的代价为$((C_A+D_A)(x+1)^2+D_Ay^2-2D_A(x+1))-((C_A+D_A)x^2+D_Ay^2-2D_Ax)=(C_A+D_A)(1+2x)-2D_Ay$
这样就可以先处理出来胜了$a_i$场的代价，然后跑费用流一场一场计入贡献即可，因为多胜一场的代价递增，所以可以直接建$A$连$T$的边即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<queue>
# include<algorithm>
using namespace std;
const int MAX=6e3+5;
struct p{
int x,y,d,cn;
}c[MAX*400];
int n,m,num=1,T,ans;
int h[MAX],C[MAX],D[MAX],a[MAX],b[MAX],cnt[MAX],d[MAX],pre[MAX];
bool use[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x,int y,int d,int cn=0)
{
c[++num]=(p){h[x],y,d,cn},h[x]=num;
c[++num]=(p){h[y],x,0,-cn},h[y]=num;
}
int EK()
{
int tot=0;
while(1)
{
queue<int> qu;
memset(d,1,sizeof(d));
d[0]=0,qu.push(0);
while(!qu.empty())
{
int tt=qu.front();
qu.pop(),use[tt]=0;
for(int i=h[tt],y;i;i=c[i].x)
if(d[y=c[i].y]>d[tt]+c[i].cn&&c[i].d)
{
d[y]=d[tt]+c[i].cn,pre[y]=i;
if(!use[y]) qu.push(y);
}
}
if(d[T]>1e7) return tot;
int l,hh=T,sum=1e9;
while(pre[hh]) l=pre[hh],sum=min(sum,c[l].d),hh=c[l^1].y;
hh=T;
while(pre[hh]) l=pre[hh],tot+=sum*c[l].cn,c[l].d-=sum,c[l^1].d+=sum,hh=c[l^1].y;
}
}
int main()
{
n=read(),m=read(),T=n+m+1;
for(int i=1;i<=n;++i)
a[i]=read(),b[i]=read(),cnt[i]=a[i],C[i]=read(),D[i]=read();
for(int i=1,s,t;i<=m;++i)
s=read(),t=read(),++cnt[s],++cnt[t],add(0,n+i,1),add(n+i,s,1),add(n+i,t,1);
for(int i=1;i<=n;++i)
{
ans+=C[i]*a[i]*a[i]+D[i]*(cnt[i]+b[i]-a[i])*(cnt[i]+b[i]-a[i]);
for(int j=a[i];j<=cnt[i];++j)
add(i,T,1,(C[i]+D[i])*(1+2*j)-2*D[i]*(cnt[i]+b[i]));
}
return printf("%d",ans+EK()),0;
}
