Kaka‘s Matrix Travels

题目：

   给出一个矩阵，求只能向下或者向右的情况下能得到的最大和。一般的是指遍历一次，而这个是可以重复走K次。每经过一次后就把该点设为0.求最大和。

算法：

   想到了用网络流做。但是建图没什么自信。看了别人的才敢开始建。建图其实也不难，就是有一个拆点处理，因为，一个点走一次后其上的值就为0了。这个处理很巧妙！就是拆点后建立两条边，一条是有价值的边，一条是没价值，但是可以通过的边。因为，虽然该点没价值，但是有可能其他点要通过它，这就是这题的巧妙之处！！！思抠以。。。。。

   给出一个分析的很好的别人画的建图模型。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 1 << 25;
const int MAXN = 5000 + 10;

//////////////////////////////
//费用流

struct Edge{
    int from,to,cap,flow,cost;
    Edge(){};
    Edge(int _from,int _to,int _cap,int _flow,int _cost)
        :from(_from),to(_to),cap(_cap),flow(_flow),cost(_cost){};
};

vector<Edge> edges;
vector<int> G[MAXN];
bool inq[MAXN];
int d[MAXN];
int p[MAXN];
int a[MAXN];
int N,K,V,src,sink;

/////////////////////////////

int matrix[MAXN][MAXN];
void init(){
    src = http://www.mamicode.com/N * N * 2; sink = src + 1;>

 
poj Kaka's Matrix Travels