首页 > 代码库 > bzoj1449 [JSOI2009]球队收益
bzoj1449 [JSOI2009]球队收益
Description
Input
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
orz huzecong
神犇的想法果然与众不同
首先看上去像网络流。这样就够了
先假设每场比赛两队都是输的，那么接下来转换的时候只要把其中一对变成赢的就好了。
考虑一支球队已经赢了x场输了y场现在要把输的y场之一变成赢的，考虑这样对答案的影响
原来是C[i]*x^2+D[i]*y^2，现在是C[i]*(x+1)^2+D[i]*(y-1)^2
那么在这支球队赢x场输y场的时候把一场输的变成赢的，对答案的贡献就是两个相减
对于一支一开始赢x场输y场的球队，我们向T连边，代价是从(x,y)变成(x+1,y-1)的代价。
然后还有从(x+1，y-1)到(x+2，y-2)……
因为是最小费用最大流，正确性显然
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x3ffffff#define S 0#define T n+m+1#define N 6010using namespace std;inline LL read(){ LL 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;}struct edge{int to,next,from,v,c;}e[10*N];struct match{int x,y;}M[100010];int head[N],from[N],dist[N],q[N];bool mrk[N];int n,m,ans,cnt=1;int a[N],b[N],C[N],D[N];inline void ins(int u,int v,int w,int c){ e[++cnt].to=v; e[cnt].v=w; e[cnt].c=c; e[cnt].from=u; e[cnt].next=head[u]; head[u]=cnt;}inline void insert(int u,int v,int w,int c){ ins(u,v,w,c); ins(v,u,0,-c);}inline bool spfa(){ for(int i=0;i<=T;i++)dist[i]=inf; int t=0,w=1; dist[S]=0;q[0]=S;mrk[S]=1; while (t!=w) { int now=q[t++];if (t==6005)t=0; for (int i=head[now];i;i=e[i].next) if(e[i].v&&dist[now]+e[i].c<dist[e[i].to]) { dist[e[i].to]=dist[now]+e[i].c; from[e[i].to]=i; if (!mrk[e[i].to]) { mrk[e[i].to]=1; q[w++]=e[i].to; if(w==6005)w=0; } } mrk[now]=0; } return dist[T]!=inf;}inline void mcf(){ int x=inf; for (int i=from[T];i;i=from[e[i].from]) x=min(x,e[i].v); for (int i=from[T];i;i=from[e[i].from]) { e[i].v-=x; e[i^1].v+=x; ans+=x*e[i].c; }}int main(){ n=read();m=read(); for (int i=1;i<=n;i++) { a[i]=read(); b[i]=read(); C[i]=read(); D[i]=read(); } for(int i=1;i<=m;i++) { M[i].x=read(); M[i].y=read(); b[M[i].x]++; b[M[i].y]++; insert(S,i,1,0); insert(i,m+M[i].x,1,0); insert(i,m+M[i].y,1,0); } for (int i=1;i<=n;i++) ans+=a[i]*a[i]*C[i]+b[i]*b[i]*D[i]; for (int i=1;i<=m;i++) { int x=M[i].x,y=M[i].y; insert(m+x,T,1,2*a[x]*C[x]-2*b[x]*D[x]+C[x]+D[x]); a[x]++;b[x]--; insert(m+y,T,1,2*a[y]*C[y]-2*b[y]*D[y]+C[y]+D[y]); a[y]++;b[y]--; } while (spfa())mcf(); printf("%d\n",ans); return 0;}
S向所有比赛连边，所有比赛向两队连边。所有队伍
bzoj1449 [JSOI2009]球队收益
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。