hdu4862：http://acm.hdu.edu.cn/showproblem.php?pid=4862
题意：给你n*m的方格，每个方格中有一个数(0---9),然后你每次可以选择一个点开始，这个点是之前没有访问过的，然后你可以向右边的的方格跳，也可以向下面的方格跳。跳的过程中，你会丢失(x2-x1)+(y2-y1)-1一些能量。如果下一个方格和现在的方格的数字相同，那么你可以得到一些能量。每次一开始，你就可以随便跳。但是你最多只能选择k次开始。为你得到的最多能量，并且每个格子只访问一次。
题解：剖析一下，就知道，这一题是求最小k条路径覆盖(如果把边权取负的话)。接下是如果求解这个模型。建图方式如下。
把原图中点分成两部分X(n*m个)，Y(n*m个)，原图中的边(u,v,w),改成(u,v+n*m,-w);然后源点与X部分的每一点建一条边(st,x,0),然后st与p之间建一条边(st,p,0),容量为k，然后p与Y的每一点建一条边，然后Y与汇点建立一条边，这些变的容量都是1，费用都是0.然后跑最小费用最大流，如果满流则能跑完每个格子一次。否则不能。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define inf 100000000
using namespace std;
const int E=;
const int N=;
struct{
int v, cap, cost, next; // re记录逆边的下标。
}edge[E];
int n, m, ans,flow;
int k, cnt,head[N];
int que[N], pre[N], dis[N];
bool vis[N];
char mp[][];
void init(){//初始化
cnt=ans=,flow=;
memset(head,-,sizeof(head));
}
void addEdge(int u, int v, int ca, int co){
edge[cnt].v = v;
edge[cnt].cap = ca;
edge[cnt].cost = co;
edge[cnt].next = head[u];
head[u] = cnt ++;
edge[cnt].v = u;
edge[cnt].cap = ;
edge[cnt].cost = -co;
edge[cnt].next = head[v];
head[v] = cnt++;
}
bool spfa(){ // 源点为0，汇点为n。
int i;
for(i = ; i <= *m*n+; i ++){
dis[i] = inf;
vis[i] = false;
}
queue<int>Q;
Q.push(*n*m+);
dis[*n*m+]=;
vis[*n*m+] = true;
while(!Q.empty()){ // 这里最好用队列，有广搜的意思，堆栈像深搜。
int u = Q.front();
Q.pop();
for(i = head[u]; i != -; 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;
Q.push(v);
}
}
}
vis[u] = false;
}
if(dis[*n*m+] == inf) return false;
return true;
}
void end(){
int u, p, sum = inf;
for(u = *n*m+; u !=*n*m+; u = edge[p^].v){//0是超级源点
p = pre[u];
sum = min(sum, edge[p].cap);
}
for(u = *n*m+; u != *n*m+; u = edge[p^].v){
p = pre[u];
edge[p].cap -= sum;
edge[p^].cap += sum;
ans += sum * edge[p].cost; // cost记录的为单位流量费用，必须得乘以流量。
}
flow+=sum;
} void input(){
memset(mp,,sizeof(mp));
for(int i=;i<=n;i++){
for(int j=;j<=m;j++)
cin>>mp[i][j];
}
}
void build(){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
for(int k=j+;k<=m;k++){
if(mp[i][j]==mp[i][k])
addEdge((i-)*m+j,(i-)*m+k+n*m,,k-j--(mp[i][j]-''));
else
addEdge((i-)*m+j,(i-)*m+k+n*m,,k-j-); }
for(int k=i+;k<=n;k++){
if(mp[i][j]==mp[k][j])
addEdge((i-)*m+j,(k-)*m+j+n*m,,k-i--(mp[i][j]-''));
else
addEdge((i-)*m+j,(k-)*m+j+n*m,,k-i-);
} }
for(int i=;i<=n*m;i++){
addEdge(*m*n+,i,,);
addEdge(,i+n*m,,);
addEdge(i+n*m,*n*m+,,);
}
addEdge(*n*m+,,k,);
}
int cas;
int main(){
int tt=;
scanf("%d",&cas);
while(cas--){
scanf("%d%d%d",&n,&m,&k);
input();
init();
build();
while(spfa())end();
if(flow==n*m){
printf("Case %d : %d\n",tt++,-ans);
}
else{
printf("Case %d : -1\n",tt++);
}
}
}