原题地址

强烈吐槽百度使我的博客里第二次出现 http 链接。

题意概述

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

给定 $n×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≤T≤20$,$1≤n≤200$,$-10^9 \leq a_{i,j} \leq 10^9(1 \leq i,j \leq n)$。

输出

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

样例

输入

输出

思路

Sadly my Chinese IME is down and I can’t type my thought here.

代码