Description

给出一个 \(n \times n\) 的矩阵 \(B\) 和一个 \(1 \times n\) 的矩阵 \(C\). 求出一个 \(1 \times n\) 的 01 矩阵 \(A\), 使得 \(D = (A \times B - C) \times A^T\) 最大. 其中 \(A^T\) 为 \(A\) 的转置.

Input

第一行输入一个整数 \(n\), 接下来 \(n\) 行输入 \(B\) 矩阵, 第 \(i\) 行第 \(j\) 个数字代表 \(B_{i,j}\);

接下来一行输入 \(n\) 个整数, 代表矩阵 \(C\). 矩阵 \(B\) 和矩阵 \(C\) 中每个数字都是不 超过 \(1000\) 的非负整数.

Output

输出最大的 \(D\)

Sample Input

3
1 2 1
3 1 0
1 2 3
2 3 7

Sample Output

2

Data Range

\(1 \leq n \leq 500\)

Explanation

首先可以保证不会爆 long long;

然后按照黄学长的说法, 应该有:

\[\sum_{i=1}^n \sum_{j=1}^n B_{ij} \cdot A_i \cdot A_j – \sum_{i=1}^n A_i \cdot C_i\]

然后最小割一发就可以了.

此题应该高亮之后再看一看

Source Code


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

using namespace std;
typedef long long lli;
const int maxN = 510, maxn = 300100, maxm = 2000100;
const int infinit = 0x0f7f7f7f;

class Dinic
{
public:
    struct edge
    {
        int u, v, flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, int flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = 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] > 0)
            return true;
        return false;
    }
    int dfs(int p, int mn)
    {
        if (p == t)
            return mn;
        int 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(mn - sum, ep->flow));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        return sum;
    }
    int eval(void)
    {
        int sum = 0, tmp;
        while (make_level()) {
            tmp = dfs(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
} graph;

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    graph.n = n + n*n + 2;
    graph.s = n + n*n + 1;
    graph.t = graph.n;
    int cnt = n;
    int sum = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int x; scanf("%d", &x);
            cnt += 1;
            graph.add_edge(i, cnt, infinit);
            graph.add_edge(j, cnt, infinit);
            graph.add_edge(cnt, graph.t, x);
            sum += x;
        }
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        graph.add_edge(graph.s, i, x);
    }
    sum -= graph.eval();
    printf("%d\n", sum);
    return 0;
}