题目地址：洛谷：【P4307】[JSOI2009]球队收益 / 球队预算 – 洛谷、BZOJ：Problem 1449. — [JSOI2009]球队收益

题目描述

在一个篮球联赛里，有n支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是Cix^2+Diy^2，Di<=Ci。(赢得多，给球员的奖金就多嘛) 其中x,y分别表示这只球队本赛季的胜负场次。现在赛季进行到了一半，每只球队分别取得了a[i]场胜利和b[i]场失利。而接下来还有m场比赛要进行。问联盟球队的最小总支出是多少。

输入输出格式

输入格式：
第一行n，m
接下来n行每行4个整数a[i],b[i],Ci,Di
再接下来m行每行两个整数s，t表示第s支队伍和第t支队伍之间将有一场比赛，注意两只队间可能有多场比赛。

输出格式：
输出总支出的最小值。

输入输出样例

输入样例#1：

3 3
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1

输出样例#1：

43

说明

对于20%的数据2<=n<=10,0<=m<=20
对于100%的数据2<=n<=5000,0<=m<=1000,0<=di<=ci<=10,0<=a[i],b[i]<=50.

题解

这个的网络模型需要来表示下面m场比赛的胜负情况，我们考虑使用费用流。对比赛和队伍建点，建立源→比赛→参与比赛的两支队伍→汇的网络，其中源→比赛→队伍的边都是容量1费用0的边。
接下来考虑一下队伍→汇的边的费用问题。对于每一支队伍，我们假设他输掉了所有后面的x场比赛，也就是说，假如我们用w代表它赢的比赛，l代表它输的比赛，最开始的时候w=a_i, l=b_i+x，那么它的收益应该是C_iw^2+D_il^2。如果它赢了1场，则w加1，l减1，收益变为了C_i(w+1)^2+D_i(l-1)^2，我们来做一发减法，发现了\Delta = 2C_iw - 2D_il + C + D。我们知道，w越大的时候，l越小，\Delta的值就越大。因此这题就是一个费用递增模型，我们可以对每一个w建一条容量1费用2C_iw - 2D_il + C + D的边，表示每赢一场比赛对答案的贡献。此时这个网络模型就完整了，答案即是默认所有队伍输掉所有比赛的收益+最小费用最大流的费用。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, cost, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int f[MAXN], dis[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];

inline bool spfa(int s, int t) {
    memset(f, 0, sizeof(f));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; inque[s] = true; f[s] = INF; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && dis[v] > dis[u] + gra[i].cost) {
                pre[v] = u; pree[v] = i;
                f[v] = std::min(f[u], gra[i].cap);
                dis[v] = dis[u] + gra[i].cost;
                if(!inque[v]) {
                    inque[v] = true;
                    que.push(v);
                }
            }
        }
    }
    return f[t];
}

int flow, cost;

inline void mcmf(int s, int t) {
    while(spfa(s, t)) {
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t];
            gra[pree[i] ^ 1].cap += f[t];
        }
        flow += f[t];
        cost += f[t] * dis[t];
    }
}

int n, m, a[MAXN], b[MAXN], c[MAXN], d[MAXN], mcnt[MAXN], u, v, sum, S, T;

// 1 ~ n team
// n+1 ~ n+m match

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint();
    S = n + m + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        a[i] = readint(); b[i] = readint(); c[i] = readint(); d[i] = readint();
    }
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint();
        mcnt[u]++; mcnt[v]++;
        addedge(S, i + n, 1, 0);
        addedge(i + n, u, 1, 0);
        addedge(i + n, v, 1, 0);
    }
    for(int i = 1; i <= n; i++) {
        int w = a[i], l = b[i] + mcnt[i];
        sum += c[i] * w * w + d[i] * l * l;
        for(int j = 1; j <= mcnt[i]; j++) {
            addedge(i, T, 1, 2 * w * c[i] - 2 * l * d[i] + c[i] + d[i]);
            w++; l--;
        }
    }
    mcmf(S, T);
    printf("%d", sum + cost);
    return 0;
}