传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1449
题目简述：
Description
Input
Output
一个整数表示联盟里所有球队收益之和的最小值。
Sample Input
3 3
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
Sample Output
43
题解：
设x为win，y为lose；
先让所有人后面比赛都会输，计算出一个preans，那么怎么处理会赢的请况呢？
很简单，就让一个人的win+1，lose-1，那么相对于之前就可以获得（c*(x+1)^2+d*（y-1）^2-c*x^2-d*y^2=2*c[i]*win[i]+c[i]+d[i]-2*d[i]*lose[i])
所以就在建一条这样的边就好了，推荐使用 zkw（速度快，代码短）；
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x7fffffff
#define maxn 1000000
int pre[maxn],v[maxn],cost[maxn],cap[maxn],lis[maxn];
int lose[],win[],in[],c[],d[],dis[],now[],sla[],mark[];
bool vis[];
int n,m,s,t,tot,ans;
using namespace std;
void ins(int a, int b, int c, int d)
{
tot++; pre[tot]=now[a]; now[a]=tot; v[tot]=b; cost[tot]=d; cap[tot]=c;
}
void insert(int a, int b, int c, int d)
{
ins(a,b,c,d); ins(b,a,,-d);
}
bool spfa()
{
int head=,tail=;
for (int i=s; i<=t; i++) dis[i]=inf;
memset(mark,,sizeof(mark));
lis[]=t; dis[t]=; mark[t]=;
while (head!=tail)
{
int x=lis[head]; mark[x]=; head++;
if(head==)head=;
for (int i=now[x]; i; i=pre[i])
{
if (dis[x]+cost[i^]<dis[v[i]] && cap[i^])
{
dis[v[i]]=dis[x]+cost[i^];
if (!mark[v[i]])
{
mark[v[i]]=;
tail++;
lis[tail]=v[i];
if(tail==)tail=;
}
}
}
}
// printf("%d\n",dis[s]);
if (dis[s]!=inf ) return true; else return false;
}
int dfs(int x, int f)
{
mark[x]=;
if (x==t) return f;
int w,used=;
for (int i=now[x]; i; i=pre[i])
{
if (!mark[v[i]] && cap[i] && dis[x]-cost[i]==dis[v[i]])
{
w=dfs(v[i],min(f-used,cap[i]));
cap[i]-=w; cap[i^]+=w;
ans+=w*cost[i];
used+=w; if (used==f) return f;
}
}
return used;
}
void zkw()
{
while(spfa())
{
mark[t]=;
while(mark[t])
{
memset(mark,,sizeof(mark));
dfs(s,inf);
}
}
}
int main()
{
scanf("%d%d",&n,&m); tot=; ans=;
for (int i=; i<=n; i++)
scanf("%d%d%d%d",&win[i],&lose[i],&c[i],&d[i]);
s=; t=n+m+;
for (int i=; i<=m; i++)
{
int u,v;
insert(s,i,,);
scanf("%d%d",&u,&v);
insert(i,u+m,,);
insert(i,v+m,,);
in[u]++; in[v]++;
}
for (int i=; i<=n; i++)
{
lose[i]+=in[i];
}
ans=;
for(int i=;i<=n;i++)
ans+=win[i]*win[i]*c[i]+lose[i]*lose[i]*d[i];
for (int i=; i<=n; i++)
for (int j=; j<=in[i]; j++)
{
//insert(i+m,t,1,c[i]*(2*win[i]+2*j-1)-d[i]*(2*lose[i]-2*j+1));
insert(i+m,t,,*c[i]*win[i]+c[i]+d[i]-*d[i]*lose[i]);
win[i]++; lose[i]--;
}
//printf("%d\n",ans);
zkw();
printf("%d\n",ans);
return ;
}