首页 > 代码库 > bozj 1449/2895: 球队预算 -- 费用流
bozj 1449/2895: 球队预算 -- 费用流
2895: 球队预算
Time Limit: 10 Sec Memory Limit: 256 MBDescription
在一个篮球联赛里，有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
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.
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 100010inline int rd(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int lj[N],fro[N],to[N],v[N],w[N],fa[N],cnt=1;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,0,-d);}int T=6010;int dis[N],q[N],from[N];bool vs[N];bool spfa(){ memset(dis,0x3f,sizeof(dis)); int l=0,r=1,x; vs[0]=1;dis[0]=q[0]=0; while(l<r) { x=q[l++];vs[x]=0; 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]]=1;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=1;i<=n;i++) { a[i]=rd();b[i]=rd();c[i]=rd();d[i]=rd(); } int x,y; for(int i=1;i<=m;i++) { x=rd();y=rd(); ins(0,i,1,0); ins(i,x+m,1,0); ins(i,y+m,1,0); ji[x]++;ji[y]++; } for(int i=1;i<=n;i++) { b[i]+=ji[i]; ans+=a[i]*a[i]*c[i]+b[i]*b[i]*d[i]; } for(int i=1;i<=n;i++) { for(int j=1;j<=ji[i];j++) { ins(i+m,T,1,2*c[i]*a[i]-2*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^1]+=tp;} ans+=dis[T]*tp; } printf("%d\n",ans); return 0;}
bozj 1449/2895: 球队预算 -- 费用流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。