http://poj.org/problem?id=3422
/*
题意：给定一个n*n的矩形方格，要求从（1,1）出发，只能往右下角走，(i + 1,j) 或者 （i + n,j）每次走完将格子里面的数累加，并将所走过的格子里面的数置零，问走k能得到的最大的数：
*/
/*
网络流的题目建图是关键，这道题目建图很难想啊！首先要拆点。这里将一个点拆分成两个点，建立两条边，一条变得流量为1,权值为 map[i][j]，另一条则是流量为无穷，权值为0了。注意这条边是为了保证在走过该店后，map[i][j]为0后，还能继续走因为它有流量且权值为0. 还有就是往右下角走建立流量为无穷权值为0的边。最后要建立的就是超级源点与汇点的边了，都是流量为k权值为0的边，保证走k次。
*/
code:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define maxn 5005
using namespace std;const int inf = 99999999;struct node
{int u,v;int c,w;int next;
}g[maxn*100];
int head[maxn],cnt,pre[maxn];
int dis[maxn],map[maxn][maxn];
bool inq[maxn];
int n,m,k,s,t,ans;//为静态表初始化
void init()
{memset(head,-1,sizeof(head));cnt = 0;
}
//加边，记住反向边去权值取反
void add(int u,int v,int c,int w)
{g[cnt].u = u; g[cnt].v = v; g[cnt].c = c; g[cnt].w = w;g[cnt].next = head[u]; head[u] = cnt++;g[cnt].u = v; g[cnt].v = u; g[cnt].c = 0; g[cnt].w = -w;g[cnt].next = head[v]; head[v] = cnt++;
}
void spfa()
{int i;queue<int>q;for (i = 0; i <= t; ++i){dis[i] = -inf;inq[i] = false;pre[i] = -1;}q.push(s); inq[s] = true;dis[s] = 0;while (!q.empty()){int u = q.front(); q.pop();inq[u] = false;for (i = head[u]; i != -1; i = g[i].next){int v = g[i].v;if (g[i].c && dis[v] < dis[u] + g[i].w){dis[v] = dis[u] + g[i].w;pre[v] = i;//注意这里记录的是这一条边了if (!inq[v]){inq[v] = true;q.push(v);}}}}
}
void MCMF()
{while (1){spfa();if (pre[t] == -1) break;int x = t,minf = inf;while (x != s){minf = min(minf,g[pre[x]].c);x = g[pre[x]].u;}x = t;while (x != s){g[pre[x]].c -= minf;g[pre[x]^1].c += minf;x = g[pre[x]].u;}ans += minf*dis[t];}
}
int main()
{int i,j;scanf("%d%d",&n,&k);int tmp = n*n;init();//关键是建边的过程for (i = 1; i <= n; ++i){for (j = 1; j <= n; ++j){scanf("%d",&map[i][j]);int x = (i - 1)*n + j;int y = x + tmp;add(x,y,1,map[i][j]);add(x,y,inf,0);if (i < n) add(y,x + n,inf,0);if (j < n) add(y,x + 1,inf,0);}}s = 0; t = 2*tmp + 1;add(s,1,k,0);add(2*tmp,t,k,0);ans = 0;MCMF();printf("%d\n",ans);return 0;
}
