首页 > 代码库 > HDU 4862 Jump 费用流
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\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 + j119 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，费用为0135 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 else164 puts("-1");165 }166 167 int main() {168 #ifdef Phantom01169 freopen("HDU4862.txt", "r", stdin);170 #endif //Phantom01171 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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。