首页 > 代码库 > 【BZOJ1449&&2895】球队预算 [费用流]
【BZOJ1449&&2895】球队预算 [费用流]
球队预算
Time Limit: 10 Sec Memory Limit: 256 MB[Submit][Status][Discuss]
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
HINT
2<=n<=5000,0<=m<=1000,0<=di<=ci<=10,0<=a[i],b[i]<=50.
Source
这题很棒棒，肯定是个费用流。我们可以首先假设所有场次都是输的，然后每次调整赢的场次来获得最小答案。
怎么建边呢？
S->比赛 流量为1，费用为0 mean : 一场比赛；
比赛->两只队伍 流量为1，费用为0 mean : 流过去则表示这支队伍获得了胜利；
队伍->T 连若干条边，流量为1，费用为 C*(2a+1)-D*(2b-1) mean : 获胜得到的收益，
为什么呢？这个可以用平方关系得到（多赢一场，少输一场）
然后用原来的答案+最小费用即可。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64; 10 11 const int ONE = 50001; 12 const int EDG = 1000001; 13 const int INF = 2147483640; 14 15 int n,m; 16 int x,y; 17 int S,T; 18 int Num[ONE]; 19 int next[EDG],first[ONE],go[EDG],from[EDG],pas[EDG],w[EDG],tot; 20 int dist[ONE],pre[ONE],vis[ONE]; 21 int tou,wei,q[ONE]; 22 int Ans; 23 24 struct power 25 { 26 int a,b,C,D; 27 }A[ONE]; 28 29 inline int get() 30 { 31 int res=1,Q=1; char c; 32 while( (c=getchar())<48 || c>57) 33 if(c==‘-‘)Q=-1; 34 if(Q) res=c-48; 35 while((c=getchar())>=48 && c<=57) 36 res=res*10+c-48; 37 return res*Q; 38 } 39 40 void Add(int u,int v,int flow,int z) 41 { 42 next[++tot]=first[u]; first[u]=tot; go[tot]=v; from[tot]=u; pas[tot]=flow; w[tot]=z; 43 next[++tot]=first[v]; first[v]=tot; go[tot]=u; from[tot]=v; pas[tot]=0; w[tot]=-z; 44 } 45 46 bool Bfs() 47 { 48 for(int i=S;i<=T;i++) dist[i] = INF; 49 dist[S] = 0; vis[S] = 1; 50 tou = 0; wei = 1; q[1] = S; 51 while(tou < wei) 52 { 53 int u = q[++tou]; 54 for(int e=first[u]; e; e=next[e]) 55 { 56 int v = go[e]; 57 if(dist[v] > dist[u] + w[e] && pas[e]) 58 { 59 dist[v] = dist[u] + w[e]; pre[v] = e; 60 if(!vis[v]) 61 { 62 vis[v] = 1; 63 q[++wei] = v; 64 } 65 } 66 } 67 vis[u] = 0; 68 } 69 return dist[T] != INF; 70 } 71 72 void Deal() 73 { 74 int x = INF; 75 for(int e=pre[T]; e; e=pre[from[e]]) x = min(x,pas[e]); 76 for(int e=pre[T]; e; e=pre[from[e]]) 77 { 78 pas[e] -= x; 79 pas[((e-1)^1)+1] += x; 80 Ans += x*w[e]; 81 } 82 } 83 84 void Build() 85 { 86 S=0; T=n+m+1; 87 for(int i=1;i<=m;i++) 88 { 89 x=get(); y=get(); 90 Add(S,i, 1,0); 91 Add(i,x+m, 1,0); Add(i,y+m, 1,0); 92 93 Num[x]++; Num[y]++; 94 A[x].b++; A[y].b++; 95 } 96 97 for(int i=1;i<=n;i++) 98 { 99 Ans += A[i].a*A[i].a * A[i].C + A[i].b*A[i].b * A[i].D;100 for(int j=1;j<=Num[i];j++)101 {102 Add(i+m,T, 1,A[i].C*(2*A[i].a+1) - A[i].D*(2*A[i].b-1) );103 A[i].a++; A[i].b--;104 }105 }106 }107 108 int main()109 {110 n=get(); m=get();111 for(int i=1;i<=n;i++)112 {113 A[i].a=get(); A[i].b=get();114 A[i].C=get(); A[i].D=get();115 }116 117 Build();118 119 while(Bfs()) Deal();120 121 printf("%d",Ans);122 123 }
【BZOJ1449&&2895】球队预算 [费用流]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。