「BZOJ1449 / 2895」[JSOI2009] 球队收益
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
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.
题解
膜拜了huzecong神犇的题解
首先假设每场比赛两队都是负。。。算出初始收益
然后考虑每次比赛，其中一队为胜
从源向每场比赛连流量1费用0的边，从比赛向这场比赛的两支队都连一条流量1费用0的边
然后考虑费用的增量：多赢一场比赛产生的收益。即(C*(w+1)^2+D*(l-1)^2)-(C*w^2+D*l^2)=2w*C-2l*D+C+D。
对于某支球队，假设后M场中其参加x场，那么最初w=win,l=lose+x，之后每赢一场w++,l–。
我们从它向汇连x条边，分别代表其赢了j场比赛时相对赢j-1场时收益的增量。由于增量递增，所以可以保证正确性。
答案为所有队伍最初收益+最小费用最大流费用。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt=1,ans,T; int last[6005],q[6005],d[6005]; int win[5005],lose[5005],C[5005],D[5005],in[6005]; int mark[6005]; struct edge{ int to,next,v,c; }e[100005]; void insert(int u,int v,int w,int c) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;e[cnt].c=c; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;e[cnt].c=-c; } bool spfa() { int head=0,tail=1; for(int i=0;i<=T;i++)d[i]=inf; memset(mark,0,sizeof(mark)); q[0]=T;d[T]=0;mark[T]=1; while(head!=tail) { int now=q[head];mark[now]=0;head++; if(head==6005)head=0; for(int i=last[now];i;i=e[i].next) if(d[now]+e[i^1].c<d[e[i].to]&&e[i^1].v) { d[e[i].to]=d[now]+e[i^1].c; if(!mark[e[i].to]) { mark[e[i].to]=1; q[tail++]=e[i].to; if(tail==6005)tail=0; } } } return d[0]!=inf; } int dfs(int x,int f) { mark[x]=1; if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(!mark[e[i].to]&&e[i].v&&d[x]-e[i].c==d[e[i].to]) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; ans+=w*e[i].c; used+=w;if(used==f)return f; } return used; } void zkw() { while(spfa()) { mark[T]=1; while(mark[T]) { memset(mark,0,sizeof(mark)); dfs(0,inf); } } } int main() { n=read();m=read();T=n+m+1; for(int i=1;i<=n;i++) win[i]=read(),lose[i]=read(),C[i]=read(),D[i]=read(); for(int i=1;i<=m;i++) { insert(0,i,1,0); int u=read(),v=read(); insert(i,m+u,1,0); insert(i,m+v,1,0); in[u]++;in[v]++; } for(int i=1;i<=n;i++) lose[i]+=in[i]; for(int i=1;i<=n;i++) ans+=win[i]*win[i]*C[i]+lose[i]*lose[i]*D[i]; for(int i=1;i<=n;i++) for(int j=1;j<=in[i];j++) { insert(m+i,T,1,2*C[i]*win[i]+C[i]+D[i]-2*D[i]*lose[i]); lose[i]--;win[i]++; } zkw(); printf("%d\n",ans); return 0; } |
计数器 9790085
OI 课件=>
OI 课件=>
黄学长 好像这里应该一开始先假设所有都是输吧？
是的