2895: 球队预算
Time Limit: 10 Sec Memory Limit: 256 MB
Description
在一个篮球联赛里，有n支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是Ci*x^2+Di*y^2，Di<=Ci。(赢得多，给球员的奖金就多嘛)
其中x,y分别表示这只球队本赛季的胜负场次。现在赛季进行到了一半，每只球队分别取得了a[i]场胜利和b[i]场失利。而接下来还有m场比赛要进行。问联盟球队的最小总支出是多少。
Input
第一行n，m
接下来n行每行4个整数a[i],b[i],Ci,Di
再接下来m行每行两个整数s，t表示第s支队伍和第t支队伍之间将有一场比赛，注意两只队间可能有多场比赛。
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
Data Limit
对于20%的数据2<=n<=10,0<=m<=20
对于100%的数据2<=n<=5000,0<=m<=1000,0<=di<=ci<=10,0<=a[i],b[i]<=50.
Data Limit
对于20%的数据2<=n<=10,0<=m<=20
对于100%的数据2<=n<=5000,0<=m<=1000,0<=di<=ci<=10,0<=a[i],b[i]<=50.
HINT
一个很巧妙的建图思想，因为对于胜负的影响我们不好表示，所以我们假定所有人都是输的，然后就可以只考虑一场胜利对其的影响
我们先从源点像每个比赛建一条流量为1，费用为0的边（每场有且只有一个队伍胜利）
然后从比赛像两支队伍i分别建一条流量为1，费用为0的边
接下来考虑如何连向汇点
首先我们肯定对于每只队伍都需要建基础分为权值的边
然后每可以多赢一场我们就建一条权值为与上一次的差的边，这个我们是可以算出来的
因为C>=D，所以权值是递增的，所以要是取边的话，一定优先取最靠前的边
所以对于每个点取的边一定是连续的，这样就映射到了每个队胜利的场数
然后这样就跑最小费用最大流就可以了
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 100010
inline int rd()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int lj[N],fro[N],to[N],v[N],w[N],fa[N],cnt=;
inline void add(int a,int b,int c,int d){fro[++cnt]=lj[a];to[cnt]=b;v[cnt]=c;w[cnt]=d;fa[cnt]=a;lj[a]=cnt;}
inline void ins(int a,int b,int c,int d){add(a,b,c,d);add(b,a,,-d);}
int T=;
int dis[N],q[N],from[N];
bool vs[N];
bool spfa()
{
memset(dis,0x3f,sizeof(dis));
int l=,r=,x;
vs[]=;dis[]=q[]=;
while(l<r)
{
x=q[l++];vs[x]=;
for(int i=lj[x];i;i=fro[i])
if(v[i]&&dis[to[i]]>dis[x]+w[i])
{
dis[to[i]]=dis[x]+w[i];
from[to[i]]=i;
if(!vs[to[i]]){vs[to[i]]=;q[r++]=to[i];}
}
}
return dis[T]<inf;
}
int n,m,a[N],b[N],c[N],d[N],ji[N],ans;
int main()
{
n=rd();m=rd();
for(int i=;i<=n;i++)
{
a[i]=rd();b[i]=rd();c[i]=rd();d[i]=rd();
}
int x,y;
for(int i=;i<=m;i++)
{
x=rd();y=rd();
ins(,i,,);
ins(i,x+m,,);
ins(i,y+m,,);
ji[x]++;ji[y]++;
}
for(int i=;i<=n;i++)
{
b[i]+=ji[i];
ans+=a[i]*a[i]*c[i]+b[i]*b[i]*d[i];
}
for(int i=;i<=n;i++)
{
for(int j=;j<=ji[i];j++)
{
ins(i+m,T,,*c[i]*a[i]-*d[i]*b[i]+c[i]+d[i]);
a[i]++;b[i]--;
}
}
int tp;
while(spfa())
{
tp=inf;
for(int i=from[T];i;i=from[fa[i]]) tp=min(tp,v[i]);
for(int i=from[T];i;i=from[fa[i]]){v[i]-=tp;v[i^]+=tp;}
ans+=dis[T]*tp;
}
printf("%d\n",ans);
return ;
}