bzoj2895 球队预算

bzoj2895 球队预算

​​ 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. 双双倍经验？

#include#include#include#include#include#define pa pair #define N 7700#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x;}int num=1,h[N],f[N],flag[N],pre[N],path[N],T,n,m,win[N],lose[N];struct node{ int y,z,next,c;}data[2200000];inline void insert1(int x,int y,int z,int c){ data[++num].y=y;data[num].z=z;data[num].c=c;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].z=0;data[num].c=-c;data[num].next=h[y];h[y]=num;}inline bool spfa(){ memset(f,0x3f,sizeof(f));memset(flag,0,sizeof(flag));memset(pre,-1,sizeof(pre));f[0]=0;flag[0]=1;queueq;q.push(0); while(!q.empty()){ int x=q.front();q.pop();flag[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z,c=data[i].c; if (f[x]+c

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。