Output
一个整数表示联盟里所有球队收益之和的最小值。
Sample Input
3 3

1 0 2 1

1 1 10 1

0 1 3 3

1 2

2 3

3 1

Sample Output
43

解法:不会,膜拜神牛

题解来自:http://blog.csdn.net/sunshinezff/article/details/51131649 尊重知识产权

直接算支出不好计算。

可以先假设所有队伍一开始都输了.

考虑每个队伍赢一场会增加多少支出.

c*(x+1)^2-d*(y-1)^2-c*x^2-d*y^2=2*c*x-2*d*y+c+d;

所以我们可以从源点向每场比赛连容量为1费用为0的边。

每场比赛向这场比赛的两支队伍连容量为1费用为0的边。

然后统计一下每支队伍参加的比赛数。

每支队伍向汇点连这支队伍的比赛数条边.

容量都为1.费用依次为当前状态再多赢1场增加的支出.

初始答案加上最小费用流即可。

///BZOJ 1449

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3FFFFFFF;
const int maxn = 6500;
struct node{
    int st, en, flow, cost, next;
    node(){}
    node(int st, int en, int flow, int cost, int next):st(st),en(en),flow(flow),cost(cost),next(next){}
}E[201000];

int num, p[maxn];
void init(){
    memset(p, -1, sizeof(p));
    num = 0;
}
void add(int st, int en, int flow, int cost){
    E[num] = node(st, en, flow, cost, p[st]);
    p[st] = num++;
    E[num] = node(en, st, 0, -cost, p[en]);
    p[en] = num++;
}
int pre[maxn];
int dis[maxn];
bool fg[maxn];
bool spfa(int st, int en)
{
    for(int i=0;i<=en;i++){
        fg[i] = 0, dis[i] = inf, pre[i]=-1;
    }
    queue<int>q;
    q.push(st);
    fg[st]=1;
    dis[st]=0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        fg[u]=0;
        for(int i=p[u];~i;i=E[i].next){
            int v = E[i].en;
            if(E[i].flow&&dis[v]>dis[u]+E[i].cost){
                dis[v] = dis[u]+E[i].cost;
                pre[v]=i;
                if(!fg[v]){
                    fg[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[en] < inf) return 1;
    return 0;
}

int solve(int st, int en){
    int ans=0;
    while(spfa(st,en)){
        int d = inf;
        for(int i=pre[en];i+1;i=pre[E[i].st]) d = min(d, E[i].flow);
        for(int i=pre[en];i+1;i=pre[E[i].st]){
            E[i].flow -= d;
            E[i^1].flow += d;
            ans += d*E[i].cost;
        }
    }
    return ans;
}

int win[maxn], lose[maxn], a[maxn], b[maxn], c[maxn], d[maxn];
int n, m, ans=0;

int main(){
    scanf("%d%d", &n,&m);
    int source = n+m+1, sink=source+1;
    for(int i=1; i<=n; i++){
        scanf("%d%d%d%d", &win[i], &lose[i], &c[i], &d[i]);
    }
    for(int i=1; i<=m; i++){
        scanf("%d%d", &a[i],&b[i]);
        lose[a[i]]++;
        lose[b[i]]++;
    }
    for(int i=1; i<=n; i++) ans += c[i]*win[i]*win[i]+d[i]*lose[i]*lose[i];
    init();
    for(int i=1; i<=m; i++){
        add(source, i, 1, 0);
        add(i, a[i]+m, 1, 0);
        add(i, b[i]+m, 1, 0);
        int tmp = c[a[i]]*(2*win[a[i]]+1)-d[a[i]]*(2*lose[a[i]]-1);
        add(a[i]+m, sink, 1, tmp);
        win[a[i]]++;
        lose[a[i]]--;
        tmp = c[b[i]]*(2*win[b[i]]+1)-d[b[i]]*(2*lose[b[i]]-1);
        add(b[i]+m, sink, 1, tmp);
        win[b[i]]++;
        lose[b[i]]--;
    }
    ans = ans + solve(source, sink);
    printf("%d\n", ans);
    return 0;
}