Kaka's Matrix Travels
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9567 Accepted: 3888

Description

On an N × N chessboard with a non-negative number in each grid, Kaka starts his matrix travels with SUM = 0. For each travel, Kaka moves one rook from the left-upper grid to the right-bottom one, taking care that the rook moves only to the right or down. Kaka adds the number to SUM in each grid the rook visited, and replaces it with zero. It is not difficult to know the maximum SUM Kaka can obtain for his first travel. Now Kaka is wondering what is the maximum SUM he can obtain after his Kth travel. Note the SUM is accumulative during the K travels.

Input

The first line contains two integers N and K (1 ≤ N ≤ 50, 0 ≤ K ≤ 10) described above. The following N lines represents the matrix. You can assume the numbers in the matrix are no more than 1000.

Output

The maximum SUM Kaka can obtain after his Kth travel.

Sample Input

```3 2
1 2 3
0 2 1
1 4 2
```

Sample Output

`15`

Source

POJ Monthly--2007.10.06, Huang, Jinsong

[Submit]   [Go Back]   [Status]   [Discuss]

There is one NxN The chessboard of , Each lattice has a nonnegative integer . Go from the top left corner to the bottom right corner , Get the weights on the path lattice （ You can only go right or down ）, And the weight of each lattice can only be obtained once , It can be understood that the lattice weight is set to 0. You can go K Time , Find the maximum weight sum .

The biggest cost is the biggest flow .

Each grid is divided into entry and exit points , From the in point to the out point, connect a line with the capacity of 1, The weight is the edge of the lattice weight , It means that the weight can only be obtained once , Another one with infinite capacity , A weight of 0 The edge of , After the representation, it can go through but not get the weight . Then connect the grids according to the transfer rules at the bottom right . Do it from top left to bottom right , The maximum flow is K The maximum cost flow of .

``` #include <cstdio>
#include <cstring>
inline int get_c(void)
{
static char *head = buf + fread_siz;
static char *tail = buf + fread_siz;
if (head == tail)
}
inline int get_i(void)
{
register int ret = ;
register int neg = false;
register int bit = get_c();
for (; bit < ; bit = get_c())
if (bit == '-')neg ^= true;
for (; bit > ; bit = get_c())
ret = ret * + bit - ;
return neg ? -ret : ret;
}
inline int min(int a, int b)
{
return a < b ? a : b;
}
const int inf = 2e9;
const int N = ;
const int M = ;
int n, m;
int s, t;
int edges;
int hd[M];
int nt[M];
int to[M];
int fl[M];
int vl[M];
int dis[M];
int pre[M];
inline bool bfs(void)
{
static int que[M];
static int inq[M];
static int head, tail;
memset(dis, -, sizeof(dis));
memset(inq, , sizeof(inq));
head = , tail = ;
que[tail++] = s;
pre[s] = -;
dis[s] = ;
inq[s] = ;
while (head != tail)
{
int u = que[head++], v; inq[u] = ;
for (int i = hd[u]; ~i; i = nt[i])
if (dis[v = to[i]] < dis[u] + vl[i] && fl[i])
{
pre[v] = i ^ ;
dis[v] = dis[u] + vl[i];
if (!inq[v])inq[que[tail++] = v] = ;
}
}
return dis[t] != -;
}
inline int minCost(void)
{
int cost = ;
while (bfs())
{
int flow = inf;
for (int i = pre[t]; ~i; i = pre[to[i]])
flow = min(flow, fl[i ^ ]);
for (int i = pre[t]; ~i; i = pre[to[i]])
fl[i] += flow, fl[i ^ ] -= flow;
cost += dis[t] * flow;
}
return cost;
}
inline void add(int u, int v, int f, int w)
{
nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; vl[edges] = +w; hd[u] = edges++;
nt[edges] = hd[v]; to[edges] = u; fl[edges] = ; vl[edges] = -w; hd[v] = edges++;
}
int G[N][N];
inline int h(int x, int y, int k)
{
return ((x - ) * n + y) << | k;
}
signed main(void)
{
n = get_i();
m = get_i();
for (int i = ; i <= n; ++i)
for (int j = ; j <= n; ++j)
G[i][j] = get_i();
memset(hd, -, sizeof(hd));
s = , t = (n*n + ) << | ;
for (int i = ; i <= n; ++i)
for (int j = ; j <= n; ++j)
add(h(i, j, ), h(i, j, ), m, ),
add(h(i, j, ), h(i, j, ), , G[i][j]);
for (int i = ; i < n; ++i)
for (int j = ; j <= n; ++j)
add(h(i, j, ), h(i + , j, ), m, );
for (int i = ; i <= n; ++i)
for (int j = ; j < n; ++j)
add(h(i, j, ), h(i, j + , ), m, );
add(s, h(, , ), m, );
add(h(n, n, ), t, m, );
printf("%d\n", minCost());
}```

@Author: YouSiki

## POJ 3422 Kaka's Matrix Travels More articles about

1. POJ 3422 Kaka&#39;s Matrix Travels（ Cost stream ）

Kaka's Matrix Travels Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6792   Accepted:  ...

2. POJ 3422 Kaka&#39;s Matrix Travels（ Minimum cost and maximum flow ）

http://poj.org/problem?id=3422 The question : To give you one N*N Of the lattice , Each grid has a number , Let you start from the top left corner , It's down to the right , The number that we've gone through becomes 0, go K Time , What is the maximum energy , Cumulative . ...

3. POJ 3422 Kaka&#39;s Matrix Travels 【 Minimum cost and maximum flow 】

The question : Kaka has a matrix , Go from the top left corner to the bottom right corner , Kaka can only go right or down at a time . The matrix is no more than 1000 The positive integer , The elements that Kaka goes through become 0, Ask Kaka if you can go k Time , Ask Kaka how much and . Ideas : The problem of minimum cost and maximum flow ...

4. POJ 3422 Kaka's Matrix Travels (K Take the number of squares ： Maximum cost flow )

The question Give a n*n Matrix of size , It is required to go from the upper left corner to the lower right corner , Each time you can only go down or to the right and get data , After taking a number from a certain position, it is only a numerical value 0, Now go from the upper left corner to the lower right corner K The maximum of times . Ideas Classic cost flow model :K Take the number of squares . structure ...

5. POJ 3422 Kaka&#39;s Matrix Travels K Take the number of squares

subject : give n*n The square matrix of , Now go from the top left m Next to the bottom right , ask m The greatest value and . analysis : Maximum cost flow . Break down the points to restrict each grid only once , What if x Split into x,xx, On the right ( Suppose there is )y,yy, below ( Suppose there is )z, ...

6. poj 3422 Kaka&#39;s Matrix Travels Cost stream

Topic link Give me a n*n Matrix , From the top left corner , Go to the lower right corner , And then back in the upper left corner , That's twice . Repeat it all k Time , Each grid has a value , What is the maximum that can be achieved , The value of a lattice can only be taken once , It turns into 0. cost ...

7. POJ 3422 Kaka&#39;s Matrix Travels（ Demolition point + Maximum cost flow ） Answer key

The question : Small A Go from the top left corner to the bottom right corner , Every grid has a value , Go through the grid and take the value away , You can only go down or to the right at a time , Ask you to go k What's the most valuable thing you can get at a time . Ideas : There is a restriction here, that is to take things away after passing through , That's the size of each grid ...

8. [poj] 3422 Kaka&#39;s Matrix Travels || Minimum cost and maximum flow

The original title is Give me a N*N Matrix of , from [1,1] To [n,n] go K Time , Go through each square and add the number above , And then the number on this lattice becomes 0. Find the maximum value that can be obtained . Maximum required , So we can make the edge weight all negative and run at the minimum cost . Because it's only the first time you pass through that point ...

9. POJ 3422 Kaka&amp;#39;s Matrix Travels （ Minimum cost and maximum flow ）

POJ 3422 Kaka's Matrix Travels link :http://poj.org/problem? id=3422 The question : There is one N*N Of the lattice , There is a number in each square . Now Kaka is going to go from the top left ...

## Random recommendation

1. summary baiduTemplate and djangoTemplate Learning from

introduce       The development work needs , Except for the two that we're going to talk about today template, There are also many templates , But their destination is the same , All for the convenience of development .       The role of templates       It's a set of template syntax , Developers can write a ...

2. Local variables accessed by inner classes must be added with final

(1) An inner class is a member of an outer class , Just like member methods of external classes , So the inner class has access to all members of the outer class , Include private Of .  (2) Inner classes cannot access local variables in outer class methods , Unless the variable is final Of ( It usually happens in ...

3. python How to judge list Is there an element in

stay python Through in and not in Key words to judge a list Whether there is an element in pythontab = ['p','y','t','h','o','n','t','a','b'] if 't' ...

4. mysql note 4 Data operation of

1 Modifying data Insert :insert into stu(id,name,age,addr) values(2," Li Si ",44," Chongqing "); 2 Modify a column updata ...

5. [leetcode-530-Minimum Absolute Difference in BST]

Given a binary search tree with non-negative values, find the minimum absolute difference between va ...

6. Code Kata: Spiral matrix javascript Realization

1 2 3 4  5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9  As shown in the figure , It's just one. 5*5 The spiral matrix of My thinking is as follows : First step : Split ...

7. 【Golang】 How to deal with it in a unified way HTTP Exception capture in request

Recently written GOLANG project , No frames , Routing httprouter Now I want to realize a requirement : Don't modify httprouter Under the premise of source code , For all registered routes handle Exception capture . Everybody knows golang Use p ...

8. Linux command 2——b

badblocks: Check for damaged blocks in the disk device -b: Specifies the block size of the disk , Company : byte -c: Check several blocks at a time -i: Always read known corrupted blocks from the file , These blocks are ignored when checking -o: The result of the check is written to the specified output file . ...

9. 【 turn 】Entity Framework course ( The second edition )

Origin I just graduated many years ago, and I wrote an article about Entity Framework The article , I didn't post the homepage, but I got it 100+ The recommendation of . Probably at that time Entity Framework Just released introduction EF Less articles . After all these years ,E ...

10. PHP 5.4.17 Release !

PHP 5.4.17 Release .2013-07-04 after 1 individual RC The last version was 2013-06-07 Of 5.4.16. Fixed about 20 individual Bug And a few security holes . Even though 5.5.0 The official version has been released . but 5.4 The update hasn't stopped yet . ...