首页 > 代码库 > hdu 4862
hdu 4862
Jump
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 478 Accepted Submission(s): 205
Problem Description
There are n*m grids, each grid contains a number, ranging from 0-9. Your initial energy is zero. You can play up to K times the game, every time you can choose any one of the grid as a starting point (but not traveled before) then you can choose a grid on the right or below the current grid to jump, but it has not traveled before. Every time you can jump as many times as you want, as long as you do not violate rules. If you are from (x1, y1) to (x2, y2), then you consume |x1-x2|+|y1-y2|-1 energies. Energy can be negative.
However, in a jump, if you start position and end position has same numbers S, then you can increase the energy value by S.
Give me the maximum energy you can get. Notice that you have to go each grid exactly once and you don’t have to play exactly K times.
However, in a jump, if you start position and end position has same numbers S, then you can increase the energy value by S.
Give me the maximum energy you can get. Notice that you have to go each grid exactly once and you don’t have to play exactly K times.
Input
The first line is an integer T, stands for the number of the text cases.
Then T cases followed and each case begin with three numbers N, M and K. Means there are N rows and M columns, you have K times to play.
Then N lines follow, each line is a string which is made up by M numbers.
The grids only contain numbers from 0 to 9.
(T<=100, N<=10，M<=10，K<=100)
Then T cases followed and each case begin with three numbers N, M and K. Means there are N rows and M columns, you have K times to play.
Then N lines follow, each line is a string which is made up by M numbers.
The grids only contain numbers from 0 to 9.
(T<=100, N<=10，M<=10，K<=100)
Output
Each case, The first you should output “Case x : ”,(x starting at 1),then output The maximum number of energy value you can get. If you can’t reach every grid in no more than K times, just output -1.
Sample Input
51 5 1919291 5 2919291 5 3919293 3 33333333333 3 2333333333
Sample Output
Case 1 : 0Case 2 : 15Case 3 : 16Case 4 : 18Case 5 : -1
Author
FZU
Source
2014 Multi-University Training Contest 1
Recommend
We have carefully selected several similar problems for you: 4871 4868 4867 4866 4865
把n * m 个点分成二部图 源点对所有在x集合的点连一条费用为0，容量为1的边，y集合的点对汇点连一条费用为0，容量为1的边，
若点a可以跳到b 则点a在x集合的点向点b在y集合的点连一条费用为0，容量为1的边。
在x集合新建一个点，从源点向他连一条费用为0,容量为K的边，在从此点向y集合的所有点连一条费用为0，容量为1的边
看看是否满流，若满流费用的相反数就是最大能量
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 8 using namespace std; 9 10 #define read() freopen("sw.in", "r", stdin) 11 12 const int MAX = 305; 13 const int INF = 1e9 + 7; 14 struct Edge {int from, to, cap, flow, cost;}; 15 vector <int> G[MAX]; 16 vector <Edge> edges; 17 int inq[MAX]; 18 int p[MAX], a[MAX]; 19 int N, M, K; 20 char str[15][15]; 21 int d[MAX]; 22 23 void add_edge(int from, int to, int cap, int cost) { 24 edges.push_back((Edge) {from, to, cap, 0, cost}); 25 edges.push_back((Edge) {to, from, 0, 0, -cost}); 26 int m = edges.size(); 27 G[from].push_back(m - 2); 28 G[to].push_back(m - 1); 29 } 30 31 bool BellmanFord(int s, int t, int &flow, int &cost) { 32 for (int i = 0; i <= t + 1; ++i) d[i] = INF; 33 memset(inq, 0, sizeof(inq)); 34 d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; 35 36 queue <int> q; 37 q.push(s); 38 while (!q.empty()) { 39 int u = q.front(); q.pop(); 40 inq[u] = 0; 41 for (int i = 0; i < G[u].size(); ++i) { 42 Edge &e = edges[ G[u][i] ]; 43 if (e.cap > e.flow && d[e.to] > d[u] + e.cost) { 44 d[e.to] = d[u] + e.cost; 45 p[e.to] = G[u][i]; 46 a[e.to] = min(a[u], e.cap - e.flow); 47 if (!inq[e.to]) { 48 q.push(e.to); 49 inq[e.to] = 1; 50 } 51 } 52 } 53 } 54 55 if (d[t] == INF) return false; 56 // printf("d[t] = %d flow = %d\n", d[t], flow); 57 flow += a[t]; 58 cost += d[t] * a[t]; 59 int u = t; 60 while (u != s) { 61 edges[ p[u] ].flow += a[t]; 62 edges[ p[u] ^ 1 ].flow -= a[t]; 63 u = edges[ p[u] ].from; 64 } 65 66 return true; 67 } 68 69 int Mincost(int s, int t) { 70 int flow = 0, cost = 0; 71 while (BellmanFord(s, t, flow, cost)); 72 //printf("fuck\n"); 73 //printf("flow = %d\n", flow); 74 return flow == N * M ? cost : 1; 75 } 76 77 int main() 78 { 79 // read(); 80 int T; 81 scanf("%d", &T); 82 int s, t; 83 for (int ca = 1; ca <= T; ++ca) { 84 scanf("%d%d%d", &N, &M, &K); 85 //printf("%d %d %d\n", N, M, K); 86 for (int i = 0; i <= 2 * N * M + 3; ++i) G[i].clear(); 87 edges.clear(); 88 89 for (int i = 0; i < N; ++i) scanf("%s", str[i]); 90 s = 2 * N * M; 91 t = s + 1; 92 add_edge(s, s + 2, K, 0); 93 for (int i = 0; i < N; ++i) { 94 for (int j = 0; j < M; ++j) { 95 add_edge(s, i * M + j, 1, 0); 96 add_edge(i * M + j + N * M, t, 1, 0); 97 add_edge(s + 2, i * M + j + N * M, 1, 0); 98 for (int k = j + 1; k < M; ++k) { 99 int v = k - j - 1;100 if (str[i][j] == str[i][k]) v -= str[i][j] - ‘0‘;101 //printf("v = %d i = %d j = %d k = %d\n", -v, i, j, k);102 add_edge(i * M + j, N * M + i * M + k, 1, v);103 }104 }105 }106 107 for (int i = 0; i < M; ++i) {108 for (int j = 0; j < N; ++j) {109 for (int k = j + 1; k < N; ++k) {110 int v = k - j - 1;111 if (str[j][i] == str[k][i]) v -= str[j][i] - ‘0‘;112 add_edge(j * M + i, k * M + i + N * M, 1, v);113 }114 }115 }116 117 118 //cout << endl;119 printf("Case %d : %d\n", ca, -Mincost(s, t));120 }121 return 0;122 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。