多校训练就这么华丽丽的到了 ，于是乎各种华丽丽的被虐也開始了。
这是多校的1002; 最小费用最大流。
题目大意：
有n*m个方格，每一个方格都一个的十进制一位的数。你能够操作K次。
对于每一次操作，你能够选择一个出发点向下或向右Jump。跳的花费是|x1-x2|+|y1-y2|-1的能量 。假设你跳的这两个位置上数字同样，那么你就会获得数字表示的能量值。
对于每一次操作，你能够这样跳随意次 ，可是每一个位置仅仅能经过一次在这K次操作中。
初始能量值是0，当操作完毕后，假设n*m个方格没有都经过过，输出“-1”，否则输出能够得到的最大能量值。
解题思路：
建立一个流量网络，一个二部图。X部分向Y部分链接的情况表示能够从一个点跳到还有一个点，超级源点和超级汇点分别同X部分的点和Y部分的点链接。在X部分中多加一个点它与源点的流量是K费用是0，与Y部分全部点链接流量是1费用是0。这表示操作K次。
以下是代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#define clear(A, X, SIZE) memset(A, X, sizeof(A[0]) * (SIZE))
#define clearall(A, X) memset(A, X, sizeof(A))
#define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE))
#define memcopy1all(A, X) memcpy(A , X ,sizeof(X))
#define max( x, y ) ( ((x) > (y)) ? (x) : (y) )
#define min( x, y ) ( ((x) < (y)) ? (x) : (y) ) using namespace std; struct node
{
int u,v,c,f,next;
} edge[21000];
char s[12][15];
const int inf=1<<30;
int head[210],cnt,dis[210],pre[210],n,m,cost,flow;
bool vis[210];
bool spfa()
{
int i,u;
clearall(pre,-1);
clearall(dis,0x3f3f3f);
clearall(vis,false);
queue <int>q;
dis[n*m*2]=0;
vis[n*m*2]=true;
q.push(n*m*2);
while(!q.empty())
{
u=q.front();
q.pop();
i=head[u];
vis[u]=false;
while(i!=-1)
{
if(edge[i].f>0&&dis[edge[i].v]>dis[u]+edge[i].c)
{
dis[edge[i].v]=dis[u]+edge[i].c;
pre[edge[i].v]=i;
if(!vis[edge[i].v])
{
vis[edge[i].v]=true;
q.push(edge[i].v);
}
}
i=edge[i].next;
}
}
if(pre[2*n*m+1]==-1)return false;
else return true;
}
void does()
{
cost=0;
flow=0;
while(spfa())
{
int max1=inf;
int p=pre[2*n*m+1];
while(p!=-1)
{
max1=min(max1,edge[p].f);
p=pre[edge[p].u];
}
p=pre[2*n*m+1];
while(p!=-1)
{
edge[p].f-=max1;
edge[p^1].f+=max1;
cost+=max1*edge[p].c;
p=pre[edge[p].u];
}
flow+=max1;
}
}
void addedge(int u,int v,int f,int c)
{
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].f=f;
edge[cnt].c=c;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].u=v;
edge[cnt].v=u;
edge[cnt].f=0;
edge[cnt].c=-c;
edge[cnt].next=head[v];
head[v]=cnt++;
}
int main()
{
int T,k,case1=1,u,v,f,c;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0; i<n; i++)
{
scanf("%s",s[i]);
}
clearall(head,-1);
cnt=0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
u=i*m+j;
for(int k=j+1; k<m; k++) //right
{
v=i*m+k+n*m;
c=k-j-1;
c=-c;
if(s[i][j]==s[i][k])c+=s[i][j]-'0';
addedge(u,v,1,-c);
}
for(int k=i+1; k<n; k++) //down
{
v=k*m+j+n*m;
c=k-i-1;
c=-c;
if(s[i][j]==s[k][j])c+=s[i][j]-'0';
addedge(u,v,1,-c);
}
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
addedge(2*n*m,i*m+j,1,0);
addedge(i*m+j+n*m,2*n*m+1,1,0);
addedge(2*n*m+2,i*m+j+n*m,1,0);
}
}
addedge(2*n*m,2*n*m+2,k,0);
does();
printf("Case %d : ",case1++);
if(flow!=n*m)puts("-1");
else printf("%d\n",-cost);
}
return 0;
}