输入一个n×m网格图，每个结点的值为0～9，可以从任意点出发不超过k次，走完每个点且仅访问每个结点一次，问最终的能量最大值。不可全部走完的情况输出-1.
初始能量为0。 而结点（x，y）可以跳跃到结点（x，y+dy）或（x+dx，y）。消耗能量为跳跃前后结点的曼哈顿距离 - 1 。若跳跃前后的结点的值相等，能量加上那个值。
具体建图可以参考这里http://blog.sina.com.cn/s/blog_6bddecdc0102uy9g.html
最小K路径覆盖其实在之前是见过的打过的，不过这次又不会了，说明之前不牢固。。。要认真点，没什么时间浪费了。
平时在求二分图的无权的最小覆盖的时候，用的就是 n - 最大匹配
那个从源点连流量为K，费用为0的边到的“那个结点”，实际上就上虚拟前驱。。。因为X集合其实就是Y集合的前驱。而起点的前驱就是没有前驱，即“那个结点”。
然后如果满流量的话，说明所有结点都走了一遍。
模板是找JM伙伴要的。。。据说伙伴是参考KH师兄的=。=
其实最近经常问JM题。。。感觉自己退步了=。=要加油！！！
#include<cstdio>
#include<set>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std; #define maxn 222
#define maxe 30000
#define inf 0x3f3f3f3f struct Edge{
int u, v, nxt, cap, cost;
}edge[maxe];
int head[maxn]; struct MinCostMaxFlow{
queue<int> que;
int add; // edges number
int vn; // total vertex number
int cost[maxn], in[maxn], pre[maxn];
bool vis[maxn];
void init(int sz){
add = ; vn = sz + ; memset(head, -, sizeof(head));
while (!que.empty()) que.pop();
}
void insert(int u, int v, int w, int c){// u, v, capacity, cost
edge[add].u = u; edge[add].v = v; edge[add].cap = w; edge[add].cost = c;
edge[add].nxt = head[u]; head[u] = add++;
edge[add].u = v; edge[add].v = u; edge[add].cap = ; edge[add].cost = -c;
edge[add].nxt = head[v]; head[v] = add++;
}
bool spfa(int s, int e){
memset(cost, 0x3f3f3f3f, sizeof(cost));
memset(in, , sizeof(in));
memset(vis, , sizeof(vis));
cost[s] = ; pre[s] = -;
que.push(s); vis[s] = true; in[s]++;
while (!que.empty()){
int u = que.front(); que.pop();
vis[u] = false;
for (int i = head[u]; i != -; i = edge[i].nxt){
int v = edge[i].v;
if (edge[i].cap > && cost[v] > cost[u] + edge[i].cost){
cost[v] = cost[u] + edge[i].cost; pre[v] = i;
if (!vis[v]){
que.push(v); vis[v] = true; in[v]++;
if (in[v] > vn) return false;
}
}
}
}
return cost[e] < inf;
}
void mincostmaxflow(int s, int e, int &mincost, int &maxflow){
mincost = , maxflow = ;
while (spfa(s, e)){
int flow = inf;
for (int i = pre[e]; i != -; i = pre[edge[i].u]){
flow = min(flow, edge[i].cap);
}
maxflow += flow;
for (int i = pre[e]; i != -; i = pre[edge[i].u]){
edge[i].cap -= flow;
edge[i ^ ].cap += flow;
}
mincost += cost[e] * flow;
}
}
}net; int nm;
char ch[][];
int main(){
int t,n,m,k,ca=;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&k);
nm = n*m;
for(int i=;i<n;++i)scanf("%s",ch[i]);
net.init(nm*+);
for(int i=;i<n;++i){
for(int j=;j<m;++j){
int u = i*m+j+;
for(int k=i+;k<n;++k){
int v = k*m+j+;
int tmp = -(k-i-);
if(ch[i][j]==ch[k][j]) tmp+=ch[i][j]-'';
net.insert(u,nm+v,,-tmp);
}
for(int k=j+;k<m;++k){
int v = i*m+k+;
int tmp = -(k-j-);
if(ch[i][j]==ch[i][k]) tmp+=ch[i][j]-'';
net.insert(u,nm+v,,-tmp);
}
}
}
for(int i=nm+;i<=nm*;++i) net.insert(nm*+,i,,);
for(int i=;i<=nm;++i) net.insert(,i,,);
net.insert(,nm*+,k,);
for(int i=nm+;i<=nm*;++i)net.insert(i,nm*+,,);
int cost,flow;
net.mincostmaxflow(,nm*+,cost,flow);
printf("Case %d : ",++ca);
if(flow==nm) printf("%d\n",-cost);
else puts("-1");
}
return ;
}