给你一个m x n (1 <= m, n <= 100)的矩阵A (0<=aij<=10000)，要求在矩阵中选择一些数，要求每一行，每一列都至少选到了一个数，使得选出的数的和尽量的小。
这个题目有个限制，不然就非常简单了，每行每列至少选择了一个数，即每行可以多选，这与平常所做的那种简单的最小费用最大流有些不一样。
那么在建图上我们需要做出一些变化
还是那样每行每列都对应一个结点
我们需要强制其每行每列都选择到了数
首先源点向每个行结点连容量为1，花费为-100000的边
每个列结点向汇点连容量为1，花费为-100000的边，
然后行结点跟列结点之间，就连容量为1，花费为相应矩阵中的数值
接着
源点向每个行结点连容量为INF，花费为0的边，
每个列结点向汇点连容量为INF，花费为0的边
这样建图之后，肯定会优先走那些花费为负的边，保证了每一行每一列都选到了点
可以自己画图试试，就可以知道为什么这样可以
然后最后的结果由于多加了一些负数，所以要变化一下
/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 111111
#define MAXN 222
#define MAXM 55555
#define L(x) x<<1
#define R(x) x<<1|1
#define eps 1e-4
using namespace std;
struct EDGE
{
int v, cap, cost, next, re; // re记录逆边的下标。
} edge[MAXM];
int n, m, ans, flow, src, des;
int e, head[MAXN];
int que[MAXN], pre[MAXN], dis[MAXN];
bool vis[MAXN];
void init()
{
e = ans = flow = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int cap, int cost)
{
edge[e].v = v;
edge[e].cap = cap;
edge[e].cost = cost;
edge[e].next = head[u];
edge[e].re = e + 1;
head[u] = e++;
edge[e].v = u;
edge[e].cap = 0;
edge[e].cost = -cost;
edge[e].next = head[v];
edge[e].re = e - 1;
head[v] = e++;
}
bool spfa()
{
int i, h = 0, t = 1;
for(i = 0; i <= n; i ++)
{
dis[i] = INF;
vis[i] = false;
}
dis[src] = 0;
que[0] = src;
vis[src] = true;
while(t != h)
{
int u = que[h++];
h %= n;
vis[u] = false;
for(i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(edge[i].cap && dis[v] > dis[u] + edge[i].cost)
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
que[t++] = v;
t %= n;
}
}
}
}
if(dis[des] == INF) return false;
return true;
}
void end()
{
int u, p, mi = INF;
for(u = des; u != src; u = edge[edge[p].re].v)
{
p = pre[u];
mi = min(mi, edge[p].cap);
}
for(u = des; u != src; u = edge[edge[p].re].v)
{
p = pre[u];
edge[p].cap -= mi;
edge[edge[p].re].cap += mi;
ans += mi * edge[p].cost; // cost记录的为单位流量费用，必须得乘以流量。
}
flow += mi;
}
int nt;
void build()
{
scanf("%d%d", &nt, &m);
src = nt + m + 1;
des = nt + m + 2;
n = des;
int num;
for(int i = 1; i <= nt; i++)
for(int j = 1; j <= m; j++)
{
scanf("%d", &num);
add(i, j + nt, 1, num);
}
for(int i = 1; i <= nt; i++)
{
add(src, i, 1, -100000);
add(src, i, INF, 0);
}
for(int i = 1; i <= m; i++)
{
add(i + nt, des, 1, -100000);
add(i + nt, des, INF, 0);
}
}
void MCMF()
{
init();
build();
while(spfa() && dis[des] < 0) end();
}
int main()
{
int T;
int cas = 0;
scanf("%d", &T);
while(T--)
{
MCMF();
printf("Case %d: %d\n", ++cas, (nt + m) * 100000 + ans);
}
return 0;
}