#P9087. 「HNOI2021 省集 Day6」一般图带权多重匹配

    ID: 5173 传统题 文件IO:match 2000ms 512MiB 尝试: 41 已通过: 3 难度: 9 上传者: 标签>CF2800省选/NOI-欧拉回路固定大小子集枚举二分图建模供需平衡建模指定流量最小费用流残量网络势能优化费用流Dijkstra增量维护

「HNOI2021 省集 Day6」一般图带权多重匹配

题目描述

给 nn 个数 aia_i,再给你一个 n×nn\times n 的矩阵 cc,无论是 aa 还是 cc,都保证是整数。

现在你可以做一类操作:

  • 将 aia_i 减一,aja_j 减一,花费 ci,jc_{i,j} 的代价。i,ji,j 可以相同,相当于 aia_i 减 22。

现在要求把 aia_i 全部变成 00,问花费最少的代价是多少,无解输出 −1-1。

输入格式

从 match.in 读入数据。

第一行为一个正整数 nn。

第二行为 nn 个整数 aia_i。

接下来 nn 行,每行 nn 个数 ci,jc_{i,j}。

输出格式

输出到 match.out 中。

仅一行一个整数,表示最小的代价。

样例

样例 1

3
2 2 2
1 4 3
4 4 5
3 5 6
10

连续两次选择 1,31,3,然后选择 2,22,2,代价为 4+3×2=104+3\times 2=10。

样例 2

2
2 39
23 9
9 23
-1

样例 3

1
2
100
100

样例 4、5

为题目附件中 match*.in 与 match*.out。

数据范围与限制

对于所有数据,满足 1≤n≤501\le n\le 50,0≤ci,j≤1050\le c_{i,j}\le 10^5,0≤ai≤1000\le a_i\le 100 且 aia_i 中至多有 1010 个奇数。

子任务编号 n≤n\le aia_i 中的奇数个数 ≤\le 特殊限制 分值
11 55 ai≤10a_i\le 10 1010
22 1414 1010 ai≤1a_i\le 1 1515
33 5050 88 如果 ii 与 jj 奇偶性不同,则 ci,j≤10c_{i,j}\le 10,否则 ci,j=105c_{i,j}=10^5 2525
44 无 5050