链接：http://poj.org/problem?id=3422

卡卡

题意：卡卡的矩阵之旅，有一个n*n的矩阵，卡卡要从左上角走到右下角，每次他只能往右或往下走，卡卡可以走k遍这个矩阵，每个点有一个num值，卡卡走到这里可以获得num点，一个点只能获得一次num值，问卡卡走完k遍后身上num值最大可以是多少？

思路：其实看到这题时没思路，图论书上说了建图的方式，但没有说为什么，我不解，网上搜了一下解题报告，百度了两页，我看到的博客都是写了如何建图，但没有写为什么要这么建。。我觉得我真是弱渣，别人看了如何建图就立即能明白，我看了如何建图还是没明白，实在找不到讲解就自己想吧！自己想其实也不算难，理解了为什么拆点这道题其实比较简单，下面是我想完之后写的：

首先，贪心是肯定不行的，贪心的想法是每次取得尽量大的sum值，如果只走一遍这么做也需要考虑走过之后的情况，贪心勉强可以做，DP做更好。但是现在要走K遍，每一次走的路都会对之后的产生影响，因为每次只能向两个方向走，需要合理的规划这K次的走法，我DP很弱，不知道DP能不能做。
再按照网络流的想法来想：要走K遍，并且每个位置都有一个值num，把num来当做流量是不可取的，因为这个值是最终的答案，是要累加起来的，而流量则取路径中最大的那一个，不是累加。
那么把什么当做流量？可以把K值当做最终的最大流，超级源点、超级汇点的弧流量都是K，这就限定了只走K遍的情况，每次走的一整条路算作一个流量，总流量为K。
那num用来做什么？num就成了网络中的限制条件，当最大流相同时选尽量大的num值，其实就是最小费用最大流，只不过现在不是取最小费用，而是取最大费用。
现在再想矩阵中该如何建图，容易想到每一点向它右边和下边连一条弧，费用可以选用这个点的num值，但容量不好取。试想，如果容量取为INF，那卡卡可以每次都走总num值最大的那条路，走K遍，因为矩阵中没有对走的次数进行限制，只在超级源汇做了限制，但一个点的num值只能取一次，这么走等于一个点的num值取了K次。那容量应该取为1吗？也不对，取1限制了一个值只会取到一次，但问题随之而来：a点到b点如果有路，这条路也只能走一次，题意中没有这个规定，题意是说一个点可以走很多次，但是值只能取一次。容量取K和取INF是一样的，也不可取。
为了解决一个值只能取一次，但一个点可以走多次的问题，就有了网上广为流传的办法：拆点。

拆点了之后a点变为a‘和a‘‘，a‘→a‘‘表示取了a点的num值，这条弧的容量为1，费用为num，再连一条端点一样的弧，容量INF，费用为0，这样保证了一个点的值只取一次。取完后向a点可以走向的b点行进，b点也同样拆成了b‘和b‘‘，a‘‘到b‘连弧，容量为INF，表示一个点可以走很多次，这样就很好的解决了刚才的问题。
其实这种题应该多做几道就能想到拆点了。

建图：上一段差不多都说了，矩阵中的建图就如上面所说，没有费用的弧只要保证容量不比K小就行了。超级源点连向矩阵左上角，容量为k，费用0，矩阵最右下角的点a‘‘连向超级汇点，容量k，费用0，建图就是这样。

理解了之后搞了很久才AC，因为在SPFA里初始化dist数组范围小了，程序陷入了死循环。

还有一点，我输出的ans是全局变量，我在主函数里又定义了一个ans，程序优先使用局部变量，无限输出0。。我debug了超久才发现。。

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 500100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define mod 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct node{
    int u,v,w,cost,next;
}edge[MAXN];
int head[5200],dist[5200],pree[5200],vis[5200];
int n,m,k,cnt,src,sink,ans,nn;
int a[60][60];
void add_edge(int a,int b,int c,int d){
    edge[cnt].v = b;
    edge[cnt].w = c;
    edge[cnt].cost = d;
    edge[cnt].next = head[a];
    head[a] = cnt++;
}
void build_graph(){
    int i,j;
    cnt = 0;
    memset(head,-1,sizeof(head));
    src = http://www.mamicode.com/0;>