bzoj2039: [2009国家集训队]employ人员雇佣

Description

作为一个富有经营头脑的富翁, 小 L 决定从本国最优秀的经理中雇佣一些来经营自己的公司. 这些经理相互之间合作有一个贡献指数, (我们用 $E_ {i, j} 表示 $i$ 经理对 $j$ 经理的了解程度), 即当经理 $i$ 和经理 $j$ 同时被雇佣时, 经理 $i$ 会对经理 $j$ 做出贡献, 使得所赚得的利润增加 $E_{i,j}$. 当然, 雇佣每一个经理都需要花费一定的金钱 $A_i$, 对于一些经理可能他做出的贡献不值得他的花费, 那么作为一个聪明的人, 小 L 当然不会雇佣他. 然而, 那些没有被雇佣的人会被竞争对手所雇佣, 这个时候那些人会对你雇佣的经理的工作造成影响, 使得所赚得的利润减少 $E_{i,j}$ (注意: 这里的 $E_{i,j}$ 与上面的 $E_{i,j}$ 是同一个). 作为一个效率优先的人, 小 L 想雇佣一些人使得净利润最大. 你可以帮助小 L 解决这个问题吗?

Input

第一行有一个整数 $n$ 表示经理的个数;

第二行有 $n$ 个整数 $A_i$ 表示雇佣每个经理需要花费的金钱;

接下来的 $n$ 行中一行包含 $n$ 个数, 表示 $E_ {i, j}, 即经理 $i$ 对经理 $j$ 的了解程度.

Output

第一行包含一个整数, 即所求出的最大值.

Sample Input

Sample Output

Data Range

20% 的数据中 $n \leq 10$

50% 的数据中 $n \leq 100$

100% 的数据中 $n \leq 1000, E_{i,j}, A_i \leq 2^{63}-1, E_{i,j} = E_{j,i}$

Explanation

这道题就是一道考查代码常数的 Dinic 最小割......

并不用多说, 只是建边的时候要魔改一下

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 1010, maxm = 10001000;
const lli infinit = 0x007f7f7f7f7f7f7fll;

class Dinic
{
public:
    struct edge
    {
        int u, v;
        lli flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, lli flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->flow = flow;
        q->next = edges[v]; edges[v] = q;
        p->rev = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        memset(level, 0, sizeof(level));
        queue<int> que;
        que.push(s);
        level[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (!level[t])
            return false;
        return true;
    }
    lli dfs(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli sum = 0, tmp;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = dfs(ep->v, min(ep->flow, mn - sum));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    lli dinic(void)
    {
        lli res = 0, tmp;
        while (make_level()) {
            tmp = dfs(s, infinit);
            if (tmp <= 0)
                break;
            res += tmp;
        }
        return res;
    }
} graph;

int n;
lli sm[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    graph.n = n + 2;
    graph.s = graph.n - 1;
    graph.t = graph.n;
    for (int i = 1, a; i <= n; i++) {
        scanf("%d", &a);
        graph.add_edge(i, graph.t, a);
    }
    lli res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1, a; j <= n; j++) {
            scanf("%d", &a);
            res += a;
            if (i >= j) continue;
            sm[i] += a; sm[j] += a;
            graph.add_edge(i, j, (lli)a * 2);
        }
    for (int i = 1; i <= n; i++)
        graph.add_edge(graph.s, i, sm[i]);
    // Cutting graph
    res -= graph.dinic();
    printf("%lld\n", res);
    return 0;
}