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;
}