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
題意：給出一個(gè)矩陣上的數(shù)字，要求從左上走到右下，每次只能向右或向下走取數(shù)，被取過的地方不再取。
求走k次的最大和。
每個(gè)點(diǎn)map[i][j]拆成兩個(gè)點(diǎn)x->x'，容量為1，消費(fèi)會(huì)map[i][j]。然后能通向x的點(diǎn)A，A'->x,容量為inf，消費(fèi)為0，x通向的點(diǎn)B，x->B',容量為inf，消費(fèi)為0.這樣保證每個(gè)點(diǎn)的值只被取一次，且能走過多次。
為了限制只走k次，矩陣左上的點(diǎn)x，加個(gè)s到0，容量為k，消費(fèi)0，矩陣的最右下的點(diǎn)y，y'->t，容量為k，消費(fèi)為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;//求最小費(fèi)用時(shí)這里得改成正無窮
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])//最大費(fèi)用，求最小費(fèi)用時(shí)這里的改符號(hào)
{
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)//求最小費(fèi)用時(shí)這里改成dit[t] < 正無窮
{
return 1;
}
return 0;
}
int MinCostFlow(int s, int t, int n)
{
if (s == t)
{
//這里具體情況具體分析，如果有附加s跟t就不用，如果用數(shù)據(jù)中的點(diǎn)作為s跟t就得考慮
//直接返回某個(gè)值。否則spfa里的隊(duì)列會(huì)死循環(huán)。
}
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;
}