#P9336. 八中公司

    ID: 5722 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>CF2000提高二分图建模带权二分图匹配KM 算法增广路二分图最大带权匹配难度分类

八中公司

题目描述

有 NN 名工人和 NN 项工作。第 ii 名工人做第 jj 项工作的效率为 aija_{ij}。每名工人恰好分配一项工作,每项工作也恰好由一名工人完成。求总效率的最大值。

输入格式

第一行一个整数 NN。接下来 NN 行,每行 NN 个整数,第 ii 行第 jj 个整数为 aija_{ij}。

输出格式

输出一个整数,表示最大总效率。

数据范围

1≤N≤2001\le N\le200。本站评测保证 1≤aij≤1011\le a_{ij}\le101。

4
62 41 86 94
73 58 11 12
69 93 89 88
81 40 69 13
329