HDU 4862 Jump 费用流

又是一个看了题解以后还坑了一天的题…… 结果最后发现是抄代码的时候少写了一个负号。

题意：

　　有一个n*m的网格，其中每个格子上都有0~9的数字。现在你可以玩K次游戏。

　　一次游戏是这样定义的: 你可以选任意之前没有走过的格子作为起点。然后走任意步，其中每一步你可以向右或者向下走任意格。假如从(x1, y1)走到(x2, y2)需要花费能量|x1-x2|+|y1-y2|-1，如果这一步和上一步格子的数字相同，那么可以获得格子上相应数字的能量。能量可以为负值。

　　问你，在K次以内走完所以格子最多能得到多少能量，若走不完，输出-1 。

思路：(直接抄题解)

　　最小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，最这个图跑最小费用最大流，如果满流就是存在解，反之不存在，最小费用的相反数就是可以获得的最大能量。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <algorithm>
  7 #include <string>
  8 #include <queue>
  9 #include <stack>
 10 #include <vector>
 11 #include <map>
 12 #include <set>
 13 #include <functional>
 14 #include <time.h>
 15 
 16 using namespace std;
 17 
 18 const int INF = 1<<29;
 19 const int MAXN = 2050;
 20 
 21 struct Edge {
 22     int from, to, cap, flow, cost;
 23     Edge(int from, int to, int cap, int flow, int cost)
 24     : from(from), to(to), cap(cap), flow(flow), cost(cost) {}
 25 };
 26 
 27 struct MCMF {
 28     int n, m, s, t;
 29     vector<Edge> edges;
 30     vector<int> G[MAXN];
 31 
 32     int inq[MAXN];
 33     int d[MAXN];
 34     int p[MAXN];
 35     int a[MAXN];
 36     int cnt[MAXN];
 37 
 38     void init(int n) {
 39         this->n = n;
 40         for (int i = 0; i < n; i++) G[i].clear();
 41         edges.clear();
 42     }
 43 
 44     void addEdge(int from, int to, int cap, int cost) {
 45         edges.push_back(Edge(from, to, cap, 0, cost));
 46         edges.push_back(Edge(to, from, 0, 0, -cost));
 47         m = edges.size();
 48         G[from].push_back(m-2);
 49         G[to].push_back(m-1);
 50     }
 51 
 52     bool BellmanFord(int s, int t, int &flow, int &cost) {
 53         for (int i = 0; i < n; i++) d[i] = INF;
 54         memset(inq, 0, sizeof(inq));
 55         memset(cnt, 0, sizeof(cnt));
 56         d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
 57 bool flag = false;
 58         queue<int> Q;
 59         Q.push(s);
 60         while (!Q.empty()) {
 61             int u = Q.front(); Q.pop();
 62 //printf("u: %d %d
", u, Q.size());
 63             inq[u] = 0;
 64             for (int i = 0; i < G[u].size(); i++) {
 65                 Edge &e = edges[G[u][i]];
 66                 if (e.cap>e.flow && d[e.to] > d[u]+e.cost) {
 67                     cnt[e.to] = cnt[u]+1;
 68                     if (cnt[e.to]>=n) {flag = true; break; }
 69 //printf("u: %d v: %d
 d[u]: %d d[v]: %d cost: %d
cap: %d flow: %d
", u, e.to, d[u], d[e.to], e.cost, e.cap, e.flow);
 70                     d[e.to] = d[u] + e.cost;
 71                     p[e.to] = G[u][i];
 72                     a[e.to] = min(a[u], e.cap-e.flow);
 73                     if (!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; }
 74                 }
 75             }
 76             if (flag)break;
 77         }
 78         if (d[t]==INF) return false;
 79         flow += a[t];
 80         cost += d[t]*a[t];
 81         int u = t;
 82         while (u!=s) {
 83             edges[p[u]].flow += a[t];
 84             edges[p[u]^1].flow -= a[t];
 85             u = edges[p[u]].from;
 86         }
 87         return true;
 88     }
 89 
 90     pair<int, int> MinCost(int s, int t) {
 91         int flow = 0, cost = 0;
 92         while (BellmanFord(s, t, flow, cost)) ;
 93         return make_pair(flow, cost);
 94     }
 95     void print(){
 96         for(int i=0;i<n;i++){
 97             printf("%d :",i);
 98             for(int j=0;j<G[i].size();j++)
 99                 printf("(%d %d %d)",edges[G[i][j]].to,edges[G[i][j]].cap,edges[G[i][j]].cost);
100             puts("");
101         }
102     }
103 }solver;
104 
105 int N, M, K;
106 int grid[15][105];
107 
108 void solve() {
109     char tmp[200];
110     scanf("%d%d%d", &N, &M, &K);
111     for (int i = 0; i < N; i++) {
112         scanf("%s", tmp);
113         for (int j = 0; j < M; j++) {
114             grid[i][j] = tmp[j] - '0';
115         }
116     }
117     int num = N*M; //总的格点数
118     //格点的编号规则： grid[i][j] = i*M + j
119 
120     //建图：
121     //编号规则：
122     /*
123     0~num : 每个点的第一部分
124     num~2*num-1 : 每个点的第二部分
125     2*num: 原点
126     2*num+1 : 额外点
127     2*num+2 :
128     */
129     int st = 2*num, ad = st+1, ed = ad+1;
130     solver.init(2*num+3);
131     for (int i = 0; i < num; i++) { //原点到第一部分的每个点有一条容量为1，费用为0的边
132         solver.addEdge(st, i, 1, 0);
133     }
134     for (int i = num; i < 2*num; i++) { //每个点的第二部分到汇点有一个容量为1，费用为0
135         solver.addEdge(i, ed, 1, 0);
136     }
137     solver.addEdge(st, ad, K, 0);
138     for (int i = num; i < 2*num; i++) { //额外点到每个点的第二部分的边
139         solver.addEdge(ad, i, 1, 0);
140     }
141     for (int i = 0; i < N; i++)
142         for  (int j = 0; j < M; j++) { //对于每一个点
143             for (int x = i+1; x < N; x++) {
144                 int cost = x-i-1;
145                 if (grid[i][j]==grid[x][j])
146                     cost -= grid[i][j];
147                 solver.addEdge(i*M+j, num+x*M+j, 1, cost);
148             }
149 
150             for (int y = j+1; y < M; y++) {
151                 int cost = y-j-1;
152                 if (grid[i][j]==grid[i][y])
153                     cost -= grid[i][j];
154                 solver.addEdge(i*M+j, num+i*M+y, 1, cost);
155             }
156         }
157 //puts("ok");
158 //solver.print();
159 
160     pair<int, int> ans = solver.MinCost(st, ed);
161     if (ans.first==num)
162         printf("%d
", -ans.second);
163     else
164         puts("-1");
165 }
166 
167 int main() {
168     #ifdef Phantom01
169         freopen("HDU4862.txt", "r", stdin);
170     #endif //Phantom01
171 
172     int Case;
173     scanf("%d", &Case);
174     for (int i = 1; i <= Case; i++) {
175         printf("Case %d : ", i);
176         solve();
177     }
178 
179     return 0;
180 }

HDU4862