「BZOJ2039」[2009国家集训队]employ人员雇佣

Description

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

Input

第一行有一个整数N1000N\leq 1000表示经理的个数 第二行有N个整数Ai表示雇佣每个经理需要花费的金钱
接下来的NN行中一行包含NN个数,表示Ei,jE_{i,j},即经理ii对经理jj的了解程度。(输入满足Ei,j=Ej,iE_{i,j}=E_{j,i}

Output

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

Sample Input

1
2
3
4
5
3
3 5 100
0 6 1
6 0 2
1 2 0

Sample Output

1
1

HINT

20%20\%的数据中N10N\leq 10
50%50\%的数据中N100N\leq 100
100%100\%的数据中 N1000N\leq 1000Ei,jmaxlongintE_{i,j}\leq maxlongint, AimaxlongintA_i\leq maxlongint

Solution

SSii连容量为j=1nei,j\sum_{j=1}^n e_{i,j}的边。
iitt连容量为aia_i的边。
iijj连容量为2ei,j2e_{i,j}的边。
答案就是ijei,jmaxflow\sum_i\sum_j e_{i,j}-maxflow

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1100, M = N * N * 2;
int head[N], en = 1;
struct Edge {
int u, v, nxt;
ll f;
}e[M * 2];
void addedge(int x, int y, ll f) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = f;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f= 0;
}
int s, t;
int d[N];
bool bfs() {
queue<int>q;
for(int i = 1; i <= t; ++i) d[i] = 0;
d[s] = 1;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
ll dinic(int x, ll flow) {
if(x == t) return flow;
ll rest = flow, k;
for(int i = head[x]; i && rest; i = e[i].nxt) if(e[i].f && d[e[i].v] == d[x] + 1) {
k = dinic(e[i].v, min(rest, e[i].f));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
if(rest == flow) d[x] = 0;
return flow - rest;
}
int n;
ll a[N], b[N][N];
const ll inf = 1e18;
int main() {
n = read();
s = n + 1;
t = n + 2;
for(int i = 1; i <= n; ++i) {
a[i] = read();
addedge(i, t, a[i]);
//addedge(s, i, inf);
}
ll ans = 0, y;
for(int i = 1; i <= n; ++i) {
ll sum = 0;
for(int j = 1; j <= n; ++j) b[i][j] = read(), sum += b[i][j];
ans += sum;
for(int j = 1; j <= n; ++j) if(j != i) addedge(i, j, 2 * b[i][j]);
addedge(s, i, sum);
/* ll sum = 0;
for(int j = 1; j < i; ++j) sum += b[i][j] * 3;
addedge(s, i + n, sum);
addedge(i + n, i, sum);
for(int j = 1; j < i; ++j) addedge(i + n, j, b[i][j]);*/
}
while(bfs()) while(y = dinic(s, inf)) ans -= y;
writeln(ans);
return 0;
}