6346：整数规划

题目描述

度度熊有一个可能是整数规划的问题：

给定 $n \times n$ 个整数 $a_{i,j}(1 \leq i,j \leq n)$，要找出 $2n$ 个整数 $x_1$,$x_2$,…,$x_n$,$y_1$,$y_2$,…,$y_n$ 在满足 $x_i+y_j \leq a_{i,j}(1 \leq i,j \leq n)$ 的约束下最大化目标函数 $\sum_{i=1}^{n} x_i + \sum_{i=1}^{n} y_i$，

你需要帮他解决这个整数规划问题，并给出目标函数的最大值。

输入解释

第一行包含一个整数 $T$，表示有 $T$ 组测试数据。

接下来依次描述 $T$ 组测试数据。对于每组测试数据：

第一行包含一个整数 $n$，表示该整数规划问题的规模。

接下来 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行第 $j$ 列的元素是 $a_{i,j}$。

保证 $ 1 \leq T \leq 20$，$1 \leq n \leq 200$，$-10^9 \leq a_{i,j} \leq 10^9(1 \leq i,j \leq n)$。

输出解释

对于每组测试数据，输出一行信息 "Case #x: y"（不含引号），其中 x 表示这是第 $x$ 组测试数据，y 表示目标函数的最大值，行末不要有多余空格。

输入样例

输出样例

Case #1: 0
Case #2: 5

来自杭电HDUOJ的附加信息

Recommend

chendu

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2018"百度之星"程序设计大赛 - 资格赛

源链接： HDU-6346

最后修改于 2020-10-25T23:30:31+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
5500/5000MS(Java/Others)	262144/262144K(Java/Others)