[bzoj 1449] [JSOI2009] 球队收益

Description

Input

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

题解懒得写了

/*
 * @Author: WildRage 
 * @Date: 2017-07-29 15:51:58 
 * @Last Modified by: WildRage
 * @Last Modified time: 2017-07-29 16:05:11
 */
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int win[5005], lose[5005];
int C[5005], D[5005], du[5005];
const int INF = 0x3f3f3f3f;
class Mincost
{
  public:
    int first[20005], p;
    Mincost()
    {
        memset(first, -1, sizeof(first));
    }
    class edge
    {
      public:
        int END, S, next, cap, cost;
    } v[100005];

    void add(int a, int b, int f, int c)
    {
        v[p].END = b, v[p].next = first[a], v[p].S = a, v[p].cap = f, v[p].cost = c, first[a] = p++;
        v[p].END = a, v[p].next = first[b], v[p].S = b, v[p].cap = 0, v[p].cost = -c, first[b] = p++;
    }
    int dis[20005], pre[20005];
    bool vis[20005];
    bool spfa(int S, int E)
    {
        memset(dis, 0x3f, sizeof(dis));
        memset(pre, -1, sizeof(pre));
        memset(vis, 0, sizeof(vis));
        queue<int> Q;
        Q.push(S);
        vis[S] = 1;
        dis[S] = 0;
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            vis[u] = 0;
            for (int i = first[u]; i != -1; i = v[i].next)
            {
                if (!v[i].cap)
                    continue;
                if (dis[v[i].END] > dis[u] + v[i].cost)
                {
                    dis[v[i].END] = dis[u] + v[i].cost;
                    pre[v[i].END] = i;
                    if (!vis[v[i].END])
                    {
                        vis[v[i].END] = 1;
                        Q.push(v[i].END);
                    }
                }
            }
        }
        return dis[E] != 0x3f3f3f3f;
    }
    int MinCost(int S, int T)
    {
        int ans = 0, flow;
        while (spfa(S, T))
        {
            flow = INF;
            for (int i = pre[T]; i != -1; i = pre[v[i].S])
                flow = min(flow, v[i].cap);
            for (int i = pre[T]; i != -1; i = pre[v[i].S])
                v[i].cap -= flow, v[i ^ 1].cap += flow;
            ans += dis[T] * flow;
        }
        return ans;
    }
} Min;
int main(int argc, char const *argv[])
{
    int n, m, a, b;
    int S = 0, T = 10005;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d%d", &win[i], &lose[i], &C[i], &D[i]);
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        Min.add(S, i, 1, 0);
        scanf("%d%d", &a, &b);
        Min.add(i, m + a, 1, 0);
        Min.add(i, m + b, 1, 0);
        du[a]++, du[b]++;
    }
    for (int i = 1; i <= n; i++)
        lose[i] += du[i];
    for (int i = 1; i <= n; i++)
        ans += lose[i] * lose[i] * D[i] + win[i] * win[i] * C[i];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= du[i]; j++)
        {
            Min.add(m + i, T, 1, 2 * win[i] * C[i] + C[i] + D[i] - 2 * lose[i] * D[i]);
            lose[i]--;
            win[i]++;
        }
    }
    printf("%d\n", ans + Min.MinCost(S, T));
    //while (1)
        ;
    return 0;
}