[BZOJ1449] [JSOI2009]球队收益 / [BZOJ2895] 球队预算

Description

在一个篮球联赛里，有n支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是Ci*x^2+Di*y2，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

Sample Output

Solution

费用流。

对于每个球队设点\(A_i\)，每场未确定的比赛设\(B_i\)，那么有一个比较显然的框架：

对于每个点\(A_i\)，\(A_i\)到\(t\)连边，容量为剩下的场次中\(i\)最多可以赢的次数，这个次数设为\(mx_i\)。
对于每个点\(B_i\)，连边\((s,B_i),(B_i,x),(B_i,y)\)，其中\(x,y\)表示这场比赛的双方，容量都为\(1\)。

很显然可以知道这个图的每一种最大流代表一种方案，现在我们的目的就是要给这个图的边加权，使得费用最小。

考虑一场比赛都没进行的时候（题目给出的结果不算），假设每支球队每场都输了，那么当前有一个总代价，然后比了一场比赛，那么必然就有一支球队输场\(-1\)，胜场\(+1\)，设原来赢了\(a\)场，输了\(b\)场，那么新增的代价就是：

\[\begin{align}
&c_i(a+1)^2+d_i(b-1)^2-c_ia^2-d_ib^2\\
=&c_i+d_i+2c_ia-2d_ib
\end{align}
\]

注意到随着胜场的增多，败场的减小，这个式子是单调递增的，也就是说，我们可以利用拆边的思想建图。

那么建图修改为：

对于每个点\(A_i\)，向\(t\)连\(mx_i\)条边，容量为\(1\)，费用依次递增，也就是上面那个式子。
其他的边费用均为\(0\)。

然后跑最小费用最大流，加上已经确定的花费，就是总代价了。

#include<bits/stdc++.h>

using namespace std;

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define sqr(x) ((x)*(x))

const int maxn = 1e5+10;

const int inf = 1e9;

int n,m,s,t,tot=1,cost;

int head[maxn],vis[maxn],dis[maxn],a[maxn],b[maxn],C[maxn],D[maxn],l[maxn],fr[maxn],pre[maxn];

struct edge{int to,nxt,w,c;}e[maxn<<1];

void add(int u,int v,int w,int c) {e[++tot]=(edge){v,head[u],w,c},head[u]=tot;}

void ins(int u,int v,int w,int c) {add(u,v,w,c),add(v,u,0,-c);}

int bfs() {

    memset(dis,63,4*(t+1));

    memset(vis,0,4*(t+1));

    queue<int > q;q.push(s);dis[s]=0,vis[s]=1;

    while(!q.empty()) {

        int now=q.front();q.pop(),vis[now]=0;

        for(int i=head[now];i;i=e[i].nxt)

            if(e[i].w>0&&dis[e[i].to]>dis[now]+e[i].c) {

                dis[e[i].to]=dis[now]+e[i].c;

                if(!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);

            }

    }return dis[t]<inf;

}

int dfs(int x,int f) {

    vis[x]=1;

    if(x==t) return cost+=f*dis[t],f;

    int used=0;

    for(int i=head[x];i;i=e[i].nxt)

        if((e[i].to==t||!vis[e[i].to])&&e[i].w>0&&dis[e[i].to]==dis[x]+e[i].c) {

            int d=dfs(e[i].to,min(f-used,e[i].w));

            if(d>0) e[i].w-=d,e[i^1].w+=d,used+=d;

            if(used==f) break;

        }return used;

}

int mcmf() {

    cost=0;while(bfs()) dfs(s,inf);return cost;

}

int main() {

	read(n),read(m);s=n+m+1,t=s+1;

	for(int i=1;i<=n;i++) read(a[i]),read(b[i]),read(C[i]),read(D[i]);

	for(int i=1,x,y;i<=m;i++) {

		read(x),read(y),l[x]++,l[y]++;b[x]++,b[y]++;

		ins(s,i+n,1,0),ins(i+n,x,1,0),ins(i+n,y,1,0);

	}

	int ans=0;

	for(int i=1;i<=n;i++) ans+=C[i]*sqr(a[i])+D[i]*sqr(b[i]);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=l[i];j++) ins(i,t,1,C[i]+D[i]+2*C[i]*a[i]-2*D[i]*b[i]),a[i]++,b[i]--;

	write(ans+mcmf());

	return 0;

}

巴特西