给你一个矩阵，你最多可以选择k条路线，k条路线的起点随意，每次行走的距离随意，但是只能往右或者下走，走过的点不能再走，而且每一步如果a->b，如果a和b的权值s相等那么就可以获得s这么多能量，每一步花费的能量是|x1 - x2| + |y1 - y2| - 1,最后问你吧所有点都遍历后获得的最大能量是多少。
思路：
每个点只能走一次，最多可以选择k条路径，要求全走完的最大，显然是费用流，我写的是最大费用最大流，（最小费用最大流也行，就是正负的问题）下面说建边。
(1) 首先虚拟出来三个点，源点s，终点e，超级远点ss。
*(2) 拆点 a -> a' 流量1，费用INF //每个点只能访问一次，INF是为了让所有的点都访 问到，这个是关键，如果 是最消费用流的话可以使 -INF
(3) ss -> s 费用0流量k //限制路径条数
(4) s -> a 费用0流量1 // 每一个点都可以当路径起点
(5) a' -> b 费用 可获得价值-花费 流量是1 // 每个点让他右和下的所有点建边
(6) a' -> e 费用0,流量1 //每个点都可以做路径终点
*(7) s -> e 费用0，流量INF // 题目说k可以不全用，排除强制用k条导致的错误
这样就行了，还有就是说明下这个题目如果可以覆盖的话根本不存在负的答案，题目的那句话是误导人的，如果出现负的，那么就直接是无解的，因为ans = mclow - n * m * INF,INF很大，只要有一个格子没被覆盖过，那么abs就直接是负值了。
#include<stdio.h> #include<string.h> #include<queue> #define N_node 220 #define N_edge 33000 #define INF 10000000 using namespace std; typedef struct { int from ,to ,next ,cost ,flow; }STAR; STAR E[N_edge]; int list[N_node] ,tot; int s_x[N_node]; int mer[N_edge]; void add(int a ,int b ,int c ,int d) { E[++tot].from = a; E[tot].to = b; E[tot].cost = c; E[tot].flow = d; E[tot].next = list[a]; list[a] = tot; E[++tot].from = b; E[tot].to = a; E[tot].cost = -c; E[tot].flow = 0; E[tot].next = list[b]; list[b] = tot; } bool spfa(int s ,int t ,int n) { for(int i = 0 ;i <= n ;i ++) s_x[i] = -1000000000; int mark[N_node] = {0}; s_x[s] = 0 ,mark[s] = 1; queue<int>q; q.push(s); memset(mer ,255 ,sizeof(mer)); while(!q.empty()) { int xin ,tou; tou = q.front(); q.pop(); mark[tou] = 0; for(int k = list[tou] ;k ;k = E[k].next) { xin = E[k].to; if(E[k].flow && s_x[xin] < s_x[tou] + E[k].cost) { mer[xin] = k; s_x[xin] = s_x[tou] + E[k].cost; if(!mark[xin]) { mark[xin] = 1; q.push(xin); } } } } return mer[t] != -1; } int M_C_Flow(int s ,int t ,int n ,int nn ,int mm) { int maxcost = 0 ,minflow ,maxflow = 0; while(spfa(s ,t ,n)) { maxflow = INF; for(int i = mer[t] ;i + 1 ;i = mer[E[i].from]) { if(minflow > E[i].flow) minflow = E[i].flow; } for(int i = mer[t] ;i + 1 ;i = mer[E[i].from]) { E[i].flow -= minflow; E[i^1].flow += minflow; maxcost += E[i].cost * minflow; } maxflow += minflow; } return maxcost; } int abss(int x) { return x < 0 ? -x : x; } int main () { int map[15][15]; int n ,m ,k ,i ,cas = 1 ,t ,j; scanf("%d" ,&t); while(t--) { scanf("%d %d %d" ,&n ,&m ,&k); char tmp[15]; for(i = 1 ;i <= n ;i ++) { scanf("%s" ,tmp); for(j = 1 ;j <= m ;j ++) map[i][j] = tmp[j-1] - '0'; } memset(list ,0 ,sizeof(list)) ,tot = 1; for(i = 1 ;i <= n ;i ++) for(j = 1 ;j <= m ;j ++) { int now = (i - 1) * m + j; add(now ,now + n * m ,INF ,1); } int s = 0 ,ss = n * m * 2 + 1 ,e = n * m * 2 + 2; add(s ,ss ,0 ,k); for(i = 1 ;i <= n ;i ++) for(j = 1 ;j <= m ;j ++) { int now = (i - 1) * m + j; add(ss ,now ,0 ,1); add(now + n * m ,e ,0 ,1); for(k = i + 1 ;k <= n ;k ++) { int to = (k - 1) * m + j; int dis = abss(i - k) - 1; if(map[i][j] == map[k][j]) add(now + n * m ,to ,map[i][j] - dis,1); else add(now + n * m ,to ,0 - dis ,1); } for(k = j + 1 ;k <= m ;k ++) { int to = (i - 1) * m + k; int dis = abss(j - k) - 1; if(map[i][j] == map[i][k]) add(now + n * m ,to ,map[i][j] - dis,1); else add(now + n * m ,to ,0 - dis ,1); } } add(ss ,e ,0 ,INF); int ans = M_C_Flow(s ,e ,e ,n ,m) - n * m * INF; if(ans < 0) ans = -1; printf("Case %d : " ,cas ++); printf("%d " ,ans); } return 0; }