题解：P4307 [JSOI2009] 球队收益 / 球队预算

· · 题解

球队的总奖金可以拆分到每一次比赛，例如，x 号球队取得的第 y 场胜利，奖金为 C_x(2y-1)。

安排比赛结果，本质是把赢和输两个结果分配给两个参赛球队。但是，这样做不好把握是否把两个结果分配给同一个球队。

我们可以先假设比赛双方都输了，算出此时的总奖金，接着，再把赢的结果分配给其中一个球队。这是分配模型，考虑费用流。由于同一球队的不同场次贡献不同，所以要把每个球队拆点，(x,y) 表示 x 号球队新取得 y 场胜利。

接下来考虑连边。首先，源点向每个表示比赛的点连边，容量为 1，费用为 0，接着，每个表示某球队取得若干场数胜利的点向汇点连边，容量为 1，费用为 0。对于每一场比赛，表示比赛的点向参赛球队拆出的每个点连边，容量为 1，如果连边连向点 (x,y)，则费用为：第 A_x+y 场胜利的贡献减去第 B_x+g_x-y+1 场失利的权值，其中，g_x 为与 x 号球队有关的比赛总场数。这个费用表示：把当前假定的最后一场失利变为胜利的代价。对于同一个 x，y 越大，这个权值越大，所以算法一定优先选择 y 小的点。跑最小费用最大流即可。

但是，点太多了，实际有用的只有约 O(m) 个点，所以跑费用流时，发现某个球队的点用完了，动态加点加边即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int res;
int n,m;
int s,t;
int A[5010],B[5010],C[5010],D[5010];
int a[10000010],b[10000010];//点的信息（所属球队、新胜利场数）
vector<int>gw[5010];//对应的比赛编号
int cnt;//当前使用的编号
int h[10000010],e[10000010],ne[10000010],w[10000010],c[10000010],idx=1;
int dis[10000010];
int pre[10000010];
bool st[10000010];
int top[5010];//i号球队目前新取得过的最高的胜利场次
int calc(int x,int y,int op){//x号球队，第y场结果为op的比赛的权值（1赢2输）
    if(op==1){
        return C[x]*(2*y-1);
    }
    else{
        return D[x]*(2*y-1);
    }
}
void add_(int a,int b,int flow,int cost){
    idx++;
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=flow;
    c[idx]=cost;
    h[a]=idx;
}
void add(int a,int b,int flow,int cost){
    add_(a,b,flow,cost);
    add_(b,a,0,-cost);
}
void newnode(int x,int y){//新建一个点，表示x号球队新取得了y场胜利
    cnt++;
    a[cnt]=x;
    b[cnt]=y;
    for(int cid:gw[x]){
        add(cid,cnt,1,calc(x,A[x]+y,1)-calc(x,B[x]+gw[x].size()-y+1,2));
    }
    add(cnt,t,1,0);
    top[x]=y;
}
bool spfa(){
    for(int i=1;i<=cnt;i++)dis[i]=0x3f3f3f3f;
    dis[s]=0;
    queue<int>q;
    q.push(s);
    while(q.size()){
        int u=q.front();
        q.pop();
        st[u]=0;
        for(int i=h[u];i;i=ne[i]){
            int v=e[i];
            if(dis[v]>dis[u]+c[i]&&w[i]){
                dis[v]=dis[u]+c[i];
                pre[v]=i;
                if(!st[v]){
                    st[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return dis[t]!=0x3f3f3f3f;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    s=m+1;
    t=m+2;
    cnt=m+2;
    for(int i=1;i<=n;i++){
        cin>>A[i]>>B[i]>>C[i]>>D[i];
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        gw[x].push_back(i);
        gw[y].push_back(i);
    }
    //首先统计已有支出和全输的支出
    for(int i=1;i<=n;i++){
        res+=C[i]*A[i]*A[i];
        res+=D[i]*(B[i]+gw[i].size())*(B[i]+gw[i].size());
    }
    for(int i=1;i<=m;i++){
        add(s,i,1,0);
    }
    for(int i=1;i<=n;i++){
        newnode(i,1);
    }
    while(spfa()){
        int u=t;
        int minn=0x3f3f3f3f;
        while(u!=s){
            minn=min(minn,w[pre[u]]);
            u=e[pre[u]^1];
        }
        res+=minn*dis[t];
        u=t;
        while(u!=s){
            if(u>m+2&&b[u]==top[a[u]])newnode(a[u],b[u]+1);
            w[pre[u]]-=minn;
            w[pre[u]^1]+=minn;
            u=e[pre[u]^1];
        }
    }
    cout<<res<<"\n";
    return 0;
}