又是一个看了题解以后还坑了一天的题…… 结果最后发现是抄代码的时候少写了一个负号。
题意:
有一个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\n", 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\n d[u]: %d d[v]: %d cost: %d\ncap: %d flow: %d\n", 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\n", -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 }
HDU 4862 Jump 费用流,布布扣,bubuko.com
原文:http://www.cnblogs.com/Phantom01/p/3864769.html