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

Hyscere · 2019-03-04 18:06:58 · 题解

费用流。

对于每个球队设点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场，那么新增的代价就是：

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

那么建图修改为：

• 对于每个点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;
}