球队预算

Time Limit: 10 Sec Memory Limit: 256 MB

Description

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

Input

第一行n，m

接下来n行每行4个整数a[i],b[i],Ci,Di

再接下来m行每行两个整数s，t表示第s支队伍和第t支队伍之间将有一场比赛，注意两只队间可能有多场比赛。

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

HINT

2<=n<=5000,0<=m<=1000,0<=di<=ci<=10,0<=a[i],b[i]<=50.

Solution

这题很棒棒，肯定是个费用流。我们可以首先假设所有场次都是输的，然后每次调整赢的场次来获得最小答案。
　　怎么建边呢？
　　　　S->比赛 流量为1，费用为0 mean : 一场比赛；
　　　　比赛->两只队伍 流量为1，费用为0 mean : 流过去则表示这支队伍获得了胜利；
　　　　队伍->T 连若干条边，流量为1，费用为 C*(2a+1)-D*(2b-1) mean : 获胜得到的收益，
　　　　为什么呢？这个可以用平方关系得到（多赢一场，少输一场）
　　然后用原来的答案+最小费用即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 50001;
const int EDG = 1000001;
const int INF = 2147483640;

int n,m;
int x,y;
int S,T;
int Num[ONE];
int next[EDG],first[ONE],go[EDG],from[EDG],pas[EDG],w[EDG],tot;
int dist[ONE],pre[ONE],vis[ONE];
int tou,wei,q[ONE];
int Ans;

struct power
{
    int a,b,C,D;
}A[ONE];

inline int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Add(int u,int v,int flow,int z)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  from[tot]=u;    pas[tot]=flow;  w[tot]=z;
    next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  from[tot]=v;    pas[tot]=0;     w[tot]=-z;
}

bool Bfs()
{
    for(int i=S;i<=T;i++) dist[i] = INF;
    dist[S] = 0;    vis[S] = 1;
    tou = 0; wei = 1; q[1] = S;
    while(tou < wei)
    {
        int u = q[++tou];
        for(int e=first[u]; e; e=next[e])
        {
            int v = go[e];
            if(dist[v] > dist[u] + w[e] && pas[e])
            {
                dist[v] = dist[u] + w[e]; pre[v] = e;
                if(!vis[v])
                {
                    vis[v] = 1;
                    q[++wei] = v;
                }
            }
        }
        vis[u] = 0;
    }
    return dist[T] != INF;
}

void Deal()
{
    int x = INF;
    for(int e=pre[T]; e; e=pre[from[e]]) x = min(x,pas[e]);
    for(int e=pre[T]; e; e=pre[from[e]])
    {
        pas[e] -= x;
        pas[((e-1)^1)+1] += x;
        Ans += x*w[e];
    }
}

void Build()
{
    S=0;    T=n+m+1;
    for(int i=1;i<=m;i++)
    {
        x=get();    y=get();
        Add(S,i, 1,0);
        Add(i,x+m, 1,0);    Add(i,y+m, 1,0);

        Num[x]++;    Num[y]++;
        A[x].b++;    A[y].b++;
    }

    for(int i=1;i<=n;i++)
    {
        Ans += A[i].a*A[i].a * A[i].C + A[i].b*A[i].b * A[i].D;
        for(int j=1;j<=Num[i];j++)
        {
            Add(i+m,T, 1,A[i].C*(2*A[i].a+1) - A[i].D*(2*A[i].b-1) );
            A[i].a++; A[i].b--;
        }
    }
}

int main()
{
    n=get();    m=get();
    for(int i=1;i<=n;i++)
    {
        A[i].a=get();    A[i].b=get();
        A[i].C=get();    A[i].D=get();
    }

    Build();

    while(Bfs()) Deal();

    printf("%d",Ans);

}