【传送门：BZOJ1449】
简要题意：
在一个篮球联赛里，有n支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是Ci*x^2+Di*y^2，Di<=Ci。(赢得多，给球员的奖金就多嘛)，其中x,y分别表示这只球队本赛季的胜负场次。现在赛季进行到了一半，每只球队分别取得了a[i]场胜利和b[i]场失利。而接下来还有m场比赛要进行。问联盟球队的最小总支出是多少。
题解：
费用流
显然，我们很难处理一场胜负对于两种球队都有影响的情况
所以我们先假设每一场比赛双方都输，然后按照胜的支出来建边
st连向每一场比赛，流量为1，费用为0
每一场比赛连向两支队伍，流量都为1，费用都为0
因为一开始假设双方都输，所以我们要设的费用+输的费用一定是赢的费用，所以得到C[i]*(x+1)^2+D[i]*(y-1)^2-C[i]*x^2-D[i]*y^2
化简得到C[i]*2*x+C[i]-D[i]*2*y+D[i]（x为胜利的场数，y为输掉的场数）
每支队伍连向ed，要连s条边（s表示剩下的比赛这支队伍上场的次数），费用为C[i]*2*w[i]+C[i]-D[i]*2*l[i]+D[i]，流量为1，且每连一条边w[i]++,l[i]--，表示这支球队胜利的情况
判断正确性：因为C[i]>=D[i]，所以当w[i]++,l[i]--后，边权会变大，而且每次费用流找增广路后，肯定找的是最小费用的增广路，所以会按照顺序，一场一场地进行输赢安排
参考代码：
#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<cmath>using namespace std;struct node{ ???int x,y,c,d,next,other; ???int el; ???node() ???{ ???????d=0; ???}}a[110000];int len,last[6100];void ins(int x,int y,int c,int d){ ???int k1=++len,k2=++len; ???a[k1].x=x;a[k1].y=y;a[k1].c=c;a[k1].d=d; ???a[k1].next=last[x];last[x]=k1; ???a[k2].x=y;a[k2].y=x;a[k2].c=0;a[k2].d=-d; ???a[k2].next=last[y];last[y]=k2; ???a[k1].other=k2; ???a[k2].other=k1;}int st,ed;int list[6100];int d[6100];bool v[6100];int ans;int pos[6100],pre[6100];bool spfa(){ ???for(int i=st;i<=ed;i++) d[i]=999999999; ???d[st]=0; ???memset(v,false,sizeof(v)); ???v[st]=true; ???int head=1,tail=2; ???list[1]=st; ???while(head!=tail) ???{ ???????int x=list[head]; ???????for(int k=last[x];k;k=a[k].next) ???????{ ???????????int y=a[k].y; ???????????if(a[k].c>0&&d[y]>d[x]+a[k].d) ???????????{ ???????????????d[y]=d[x]+a[k].d; ???????????????pos[y]=x; ???????????????pre[y]=k; ???????????????if(v[y]==false) ???????????????{ ???????????????????v[y]=true; ???????????????????list[tail++]=y; ???????????????} ???????????} ???????} ???????head++; ???????v[x]=false; ???} ???if(d[ed]==999999999) return false; ???else return true;}int w[5100],l[5100],C[5100],D[5100];void Flow(){ ???while(spfa()) ???{ ???????ans+=d[ed]; ???????for(int x=ed;x!=st;x=pos[x]) ???????{ ???????????a[pre[x]].c--; ???????????a[a[pre[x]].other].c++; ???????} ???}}int s[5100];int main(){ ???int n,m; ???scanf("%d%d",&n,&m); ???for(int i=1;i<=n;i++) scanf("%d%d%d%d",&w[i],&l[i],&C[i],&D[i]); ???int sum=0; ???st=0;ed=m+n+1; ???memset(s,0,sizeof(s)); ???for(int i=1;i<=m;i++) ???{ ???????int x,y; ???????scanf("%d%d",&x,&y); ???????s[x]++;s[y]++; ???????ins(st,i,1,0); ???????ins(i,x+m,1,0); ???????ins(i,y+m,1,0); ???????l[x]++;l[y]++; ???} ???for(int i=1;i<=n;i++) ans+=C[i]*w[i]*w[i]+D[i]*l[i]*l[i]; ???//C[i]*2*w[i]+C[i]-D[i]*2*l[i]+D[i] ???for(int i=1;i<=n;i++) ???{ ???????for(int j=1;j<=s[i];j++) ???????{ ???????????ins(i+m,ed,1,C[i]*2*w[i]+C[i]-D[i]*2*l[i]+D[i]); ???????????w[i]++;l[i]--; ???????} ???} ???Flow(); ???printf("%d\n",ans); ???return 0;}BZOJ1449: [JSOI2009]球队收益
原文地址：https://www.cnblogs.com/Never-mind/p/8536373.html