bzoj#P2039. [2009国家集训队]employ人员雇佣

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

题目描述

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

输入格式

第一行有一个整数 NN 表示经理的个数。
第二行有 NN 个整数 AiA_i 表示雇佣每个经理需要花费的金钱。
接下来的 NN 行中一行包含 NN 个数,表示 Ei,jE_{i,j},即经理 ii 对经理 jj 的了解程度。

输出格式

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

样例输入

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

样例输出

1

数据规模与约定

对于 20%20\% 的数据,N10N \leq 10
对于 50%50\% 的数据,N100N \leq 100
对于 100%100\% 的数据,N103N \leq 10^3Ei,j2311E_{i,j} \leq 2^{31}-1Ai2311A_i \leq 2^{31}-1Ei,j=Ej,iE_{i,j}=E_{j,i}

题目来源

版权所有者:林衍凯