【JSOI2009】球队收益 | Mrsrz's blog

费用流

题目大意：

有 $n$ 支球队，第 $i$ 支球队目前已经赢了 $a_i$ 场，输了 $b_i$ 场。最终，赢 $x$ 场，输 $y$ 场，球队要支出 $C_i\times x^2+D_i\times y^2$ 元（$C_i\geq D_i$）。

现在还有 $m$ 场比赛，每场比赛在两个队之间进行，且必定分出胜负。

问，在所有可能的胜负情况中，所有球队的总支出最少可能是多少。

题解：

考虑网络流。

对每支球队建点，对每场比赛建点。比赛点向比赛对应的队伍连容量 $1$，费用 $0$ 的边，源点向比赛点建容量 $1$，费用 $0$ 的边。这样处理完了胜负的决策。

但是一支球队不论胜负，都有收益，而且收益和胜负的场数的平方成正比。

平方收益可以拆贡献：$x^2=1+3+5+\dots+(2x-1)$，即赢第 $k$ 场的收益为 $C_i\times(2k-1)$，输第 $k$ 场的收益为 $D_i\times(2k-1)$。

考虑先默认所有球队都输光了。对于 $1$ 的流量，我们把它看成将一次输球转化为赢球，那么多出的贡献就是再赢一场球的收益减去最后输的那场球的收益。

我们要使总收益最小，跑最小费用最大流即可。由于使得费用最小，上面拆出的贡献肯定会先走贡献小的边，所以计算是正确的。

Code：

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=6813;
int a[N],b[N],C[N],D[N],head[N],cnt=1,n,m,T,dis[N],ans,iter[N];
int dg[N];
bool vis[N];
queue<int>q;
struct edge{
    int to,nxt,cap,cost;
}e[2000000];
inline void addedge(int u,int v,int cap,int cost){
    e[++cnt]=(edge){v,head[u],cap,cost},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0,-cost},head[v]=cnt;
}
int dfs(int u,int f){
    if(!f||u==T)return f;
    vis[u]=1;
    int ret=0;
    for(int&i=iter[u];i;i=e[i].nxt)
    if(e[i].cap&&!vis[e[i].to]&&dis[e[i].to]==dis[u]+e[i].cost){
        int d=dfs(e[i].to,min(f,e[i].cap));
        e[i].cap-=d,e[i^1].cap+=d,ret+=d,f-=d;
        if(!f)break;
    }
    vis[u]=0;
    return ret;
}
bool MCMF(){
    memset(dis,0x3f,(T+1)<<2);
    dis[0]=0;
    for(q.push(0);!q.empty();){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        if(e[i].cap&&dis[e[i].to]>dis[u]+e[i].cost){
            dis[e[i].to]=dis[u]+e[i].cost;
            if(!vis[e[i].to])vis[e[i].to]=1,q.push(e[i].to);
        }
    }
    if(dis[T]>1e9)return 0;
    memcpy(iter,head,(T+1)<<2);
    ans+=dis[T]*dfs(0,0x3f3f3f3f);
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    T=n+m+1;
    for(int i=1;i<=n;++i)cin>>a[i]>>b[i]>>C[i]>>D[i];
    for(int i=n+1;i<=n+m;++i){
        addedge(0,i,1,0);
        int s,t;
        cin>>s>>t;
        addedge(i,s,1,0),addedge(i,t,1,0);
        ++dg[s],++dg[t];
    }
    for(int i=1;i<=n;++i){
        ans+=a[i]*a[i]*C[i]+(b[i]+dg[i])*(b[i]+dg[i])*D[i];
        for(int l=2*a[i]+1,r=2*(b[i]+dg[i])-1;l<=2*(a[i]+dg[i])-1;l+=2,r-=2)
        addedge(i,T,1,l*C[i]-r*D[i]);
    }
    while(MCMF());
    cout<<ans<<'\n';
    return 0;
}