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 2
1 2 3
0 2 1
1 4 2

Sample Output

15
题意：给出一个矩阵上的数字，要求从左上走到右下，每次只能向右或向下走取数，被取过的地方不再取。
求走k次的最大和。
每个点map[i][j]拆成两个点x->x'，容量为1，消费会map[i][j]。然后能通向x的点A，A'->x,容量为inf，消费为0，x通向的点B，x->B',容量为inf，消费为0.这样保证每个点的值只被取一次，且能走过多次。
为了限制只走k次，矩阵左上的点x，加个s到0，容量为k，消费0，矩阵的最右下的点y，y'->t，容量为k，消费为0.
#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;
    }
    int head, tail;
    head = tail = 0;
    for (i = 0; i <= n; i++) dis[i] = -1;//求最小费用时这里得改成正无穷
    que[tail++] = s, pre[s] = s, dis[s] = 0, visit[s] = 1;
    while (head != tail)
    {
        int u = que[head++];
        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;
                add(x, x + num, 1, map[i][j]);
                add(x, x + num, inf, 0);
                if (i + 1 < n)
                {
                    add(x + num, x + n, inf, 0);
                }
                if (j + 1 < n)
                {
                    add(x + num, x + 1, inf, 0); 
                }
            }
        }
        s = 2 * n * n, t = s + 1, n = t + 1;
        add(s, 0, m, 0);
        add(s - 1, t, m, 0);
        ans = MinCostFlow(s, t, t + 1);
        printf("%d\n", ans);
    }
    return 0;
}