最小K路径覆盖的模型，用费用流或者KM算法解决，构造二部图，X部有N*M个节点，源点向X部每个节点连一条边，流量1，费用0，Y部有N*M个节点，每个节点向汇点连一条边，流量1，费用0，如果X部的节点x可以在一步之内到达Y部的节点y，那么就连边x->y，费用为从x格子到y格子的花费能量减去得到的能量，流量1，再在X部增加一个新的节点，表示可以从任意节点出发K次，源点向其连边，费用0，流量K，这个点向Y部每个点连边，费用0，流量1，最这个图跑最小费用最大流，如果满流就是存在解，反之不存在，最小费用的相反数就是可以获得的最大能量。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4862

题解来自：http://blog.sina.com.cn/s/blog_6bddecdc0102uy9g.html 

/*
 * Author: Haipz
 * School: HDU
 * File Name: 4862.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

const int T = 100, N = 10, M = 10, K = 100;
char mat[N + 5][M + 5];
struct node {
    int x, y;
    void insert(int tx, int ty) {
        x = tx, y = ty;
        return;
    }
} H[N*M*2 + 5], G[N*M*2 + 5];
struct edge {
    int u, v, cap, cost;
    edge *net, *opt;
    void insert(int tu, int tv, int tcap, int tcost, edge *tnet) {
        u = tu, v = tv, cap = tcap, cost = tcost, net = tnet;
        return;
    }
} f[N*M*N*M*2 + 5], *link[N*M*2 + 5], *pre[N*M*2 + 5];
int dis[N*M*2 + 5];
bool vis[N*M*2 + 5];
queue<int> Q;

void addEdge(int &num, int u, int v, int cap, int cost) {
    f[++num].insert(u, v, cap, cost, link[u]), link[u] = &f[num], f[num].opt = &f[num + 1];
    f[++num].insert(v, u, 0, -cost, link[v]), link[v] = &f[num], f[num].opt = &f[num - 1];
    return;
}

bool SPFA(int s, int t, int n) {
    while (!Q.empty()) Q.pop();
    memset(vis, false, sizeof(vis));
    memset(pre, 0, sizeof(pre));
    fill(dis, dis + n, INT_MAX - 100);
    vis[s] = true, dis[s] = 0, Q.push(s);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop(), vis[u] = false;
        for (edge *p = link[u]; p; p = p->net) {
            if (p->cap && dis[u] < dis[p->v] - p->cost) {
                dis[p->v] = dis[u] + p->cost, pre[p->v] = p;
                if (!vis[p->v]) Q.push(p->v), vis[p->v] = true;
            }
        }
    }
    if (dis[t] == INT_MAX - 100) return false;
    return true;
}

void MCMF(int &mincost, int &sumflow, int s, int t, int n) {
    mincost = 0, sumflow = 0;
    while (SPFA(s, t, n)) {
        int minflow = INT_MAX - 99;
        for (edge *p = pre[t]; p; p = pre[p->u]) minflow = min(minflow, p->cap);
        for (edge *p = pre[t]; p; p = pre[p->u]) p->cap -= minflow, p->opt->cap += minflow;
        sumflow += minflow, mincost += dis[t]*minflow;
    }
    return;
}

int main() {
    int t, ics = 0;
    scanf("%d", &t);
    while (t--) {
        memset(link, 0, sizeof(link));
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 0; i < n; ++i) scanf("%s", mat[i]);
        int num = 0;
        addEdge(num, 0, 1, k, 0);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                addEdge(num, 0, i*m + j + 2, 1, 0);
                for (int r = i + 1; r < n; ++r) {
                    int energy = r - i - 1;
                    if (mat[i][j] == mat[r][j]) energy -= mat[i][j] - '0';
                    addEdge(num, i*m + j + 2, n*m + r*m + j + 2, 1, energy);
                }
                for (int c = j + 1; c < m; ++c) {
                    int energy = c - j - 1;
                    if (mat[i][j] == mat[i][c]) energy -= mat[i][j] - '0';
                    addEdge(num, i*m + j + 2, n*m + i*m + c + 2, 1, energy);
                }
                addEdge(num, n*m + i*m + j + 2, n*m*2 + 2, 1, 0);
                addEdge(num, 1, n*m + i*m + j + 2, 1, 0);
            }
        int mincost, sumflow;
        MCMF(mincost, sumflow, 0, n*m*2 + 2, n*m*2 + 3);
        printf("Case %d : ", ++ics);
        if (sumflow == n*m) printf("%d\n", -mincost);
        else printf("-1\n");
    }
    return 0;
}
转载保留版权：http://haipz.com/blog/i/5321 - 海胖博客