题目大意是说有一个B矩阵，现在A是一个空矩阵（每个元素都为0）,每次操作可以将A矩阵相邻的两个元素同时+1，但是有个要求就是A矩阵的每个元素都不可以超过K，求
这个的最小值
解题思路是这样的，新建起点与奇点（i != j）连K条边，第i条边的权值为(i - B)^2 - (i - 1 - B)^2 = 2 * i - 1 - 2 * B（这样可以保证如果此边的流量为a, 花费始终是(a-b)^2）;另外新建终点与偶点相连，代价与上诉一致；
然后跑一遍最小费用流，知道cost>=0时为止。祥见代码：
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf (-((LL)1<<40))
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)
#define rep(i, a, b) for(int i = a; i <= b; i ++) template<class T> T CMP_MIN(T a, T b) { return a < b; }
template<class T> T CMP_MAX(T a, T b) { return a > b; }
template<class T> T MAX(T a, T b) { return a > b ? a : b; }
template<class T> T MIN(T a, T b) { return a < b ? a : b; }
template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; } //typedef __int64 LL;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const double eps = 1e-; const int dx[] = {, , , -};
const int dy[] = {, , -, };
int T, N, M, K, B, ans = ; /*******************************************************************/
struct Edge {
int to, cap, flow, cost, next;
Edge(){}
Edge(int _n, int _v, int _c, int _f, int _cost){
next = _n; to = _v; cap = _c;
flow = _f; cost = _cost;
}
}; struct MCMF
{
int n, m, src, des;
int head[MAXN], tot;
Edge edges[MAXM];
int inq[MAXN];
int d[MAXN];
int p[MAXN];
int a[MAXN]; void init(int n) {
this->tot = ;
this->n = n;
mem1(head);
} void add_edge(int from, int to, int cap, int cost) {
edges[tot] = Edge(head[from], to, cap, , cost);
head[from] = tot ++;
edges[tot] = Edge(head[to], from, , , -cost);
head[to] = tot ++;
} bool bellman_ford(int s, int t, int& flow) {
for(int i = ; i < n; i ++) {
d[i] = INF;
inq[i] = ;
}
d[s] = ; inq[s] = ;
p[s] = ; a[s] = INF; queue<int>Q;
Q.push(s);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = head[u]; i != -; i = edges[i].next) {
int v = edges[i].to;
if(edges[i].cap > edges[i].flow && d[v] > d[u] + edges[i].cost) {
d[v] = d[u] + edges[i].cost;
p[v] = i;
a[v] = min(a[u], edges[i].cap - edges[i].flow);
if(!inq[v]) {
Q.push(v);
inq[v] = ;
}
}
}
}
if(d[t] >= ) return false; flow += a[t];
ans += d[t] * a[t]; int u = t;
while(u != s) {
edges[p[u]].flow += a[t];
edges[p[u]^].flow -= a[t];
u = edges[p[u]^].to;
}
return true;
} int min_cost(int s, int t) {
int flow = ;
while(bellman_ford(s, t, flow));
return ans;
} };
/***************************************************************/ int idx(int i, int j) {
return (i - ) * M + j;
} int ok(int i, int j) {
return (i >= && i <= N && j >= && j <= M);
} MCMF mcmf; int main()
{
//FIN;
cin >> T;
rep (t, , T) {
scanf("%d %d %d", &N, &M, &K);
mcmf.init(N * M + );
mcmf.src = ; mcmf.des = N * M + ; ans = ;
rep (i, , N) rep (j, , M) {
scanf("%d", &B);
ans += B * B;
if(i % == j % ) rep (k, , K) {
mcmf.add_edge(mcmf.src, idx(i, j), , * k - - * B);
rep (k, , ) if(ok(i + dx[k], j + dy[k])) {
mcmf.add_edge(idx(i, j), idx(i + dx[k], j + dy[k]), INF, );
}
}
else rep (k, , K) {
mcmf.add_edge(idx(i, j), mcmf.des, , * k - - * B);
}
}
printf("Case %d: %d\n", t, mcmf.min_cost(mcmf.src, mcmf.des));
}
return ;
}