Kaka's Matrix Travels

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 21 2 30 2 11 4 2`

Sample Output

`15`

#include <stdio.h>
#include
<stdlib.h>
#define M 200001
#define maxx 2000
#define Max(a, b) a > b ? a : b
#define Min(a, b) a < b ? a : b
#define inf (1 << 29)
struct T
{

int u, v, val, next, cost;
}e[M];
int th;
int visit[M], pre[M], dis[M], que[M], g[M], pos[M], map[100][100];
void add(int u, int v, int val, int cost)
{
e[th].u
= u, e[th].v = v, e[th].val = val, e[th].cost = cost;
e[th].next
= g[u], g[u] = th++;
e[th].u
= v, e[th].v = u, e[th].val = 0, e[th].cost = -cost;
e[th].next
= g[v], g[v] = th++;
}
int spfa(int s, int t, int n)
{

int i, u, v, k;

for (i = 0; i <= n; i++)
{
pre[i]
= -1, visit[i] = 0;
}

= tail = 0;

for (i = 0; i <= n; i++) dis[i] = -1;//求最小费用时这里得改成正无穷
que[tail++= s, pre[s] = s, dis[s] = 0, visit[s] = 1;

{

visit[u]
= 0;

for (k = g[u]; k != -1; k = e[k].next)
{
v
= e[k].v;

if (e[k].val > 0 && dis[u] + e[k].cost > dis[v])//最大费用，求最小费用时这里的改符号
{
dis[v]
= dis[u] + e[k].cost;
pre[v]
= u;
pos[v]
= k;

if (!visit[v])
{
visit[v]
= 1;
que[tail
++= v;
}
}
}
}

if (pre[t] != -1 && dis[t] > -1)//求最小费用时这里改成dit[t] < 正无穷
{

return 1;
}

return 0;
}
int MinCostFlow(int s, int t, int n)
{

if (s == t)
{

//这里具体情况具体分析，如果有附加s跟t就不用，如果用数据中的点作为s跟t就得考虑

//直接返回某个值。否则spfa里的队列会死循环。
}

int flow = 0, cost = 0;

while (spfa(s, t, n))
{

int u, min = inf;

for (u = t; u != s; u = pre[u])
{
min
= Min(min, e[pos[u]].val);
}
flow
+= min;
cost
+= dis[t] * min;

for (u = t; u != s; u = pre[u])
{
e[pos[u]].val
-= min;
e[pos[u]
^1].val += min;
}
}

return cost;
}
int main()
{

int n, m, i, j, k, s, t, u, v, cost, ans, x, num, tt;

while (scanf("%d%d"&n, &m) - EOF)
{

for (i = 0, th = 0; i < n * n * 3 + 2; i++)
{
g[i]
= -1;
}

for (i = 0; i < n; i++)
{

for (j = 0; j < n; j++)
{
scanf(
"%d"&map[i][j]);
}
}
num
= n * n;

for (i = 0; i < n; i++)
{

for (j = 0; j < n; j++)
{
x
= i * n + j;
+ num, 1, map[i][j]);
+ num, inf, 0);

if (i + 1 < n)
{
+ num, x + n, inf, 0);
}

if (j + 1 < n)
{
+ num, x + 1, inf, 0);
}
}
}
s
= 2 * n * n, t = s + 1, n = t + 1;