原题链接：http://codevs.cn/problem/1227/

题目描述 

Description

给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

输入描述 

Input Description

第一行两个数n,k（1<=n<=50, 0<=k<=10）

接下来n行,每行n个数,分别表示矩阵的每个格子的数

输出描述 

Output Description

一个数,为最大和

样例输入 

Sample Input

3 1

1 2 3

0 2 1

1 4 2

样例输出 

Sample Output

11

数据范围及提示 

Data Size & Hint

1<=n<=50, 0<=k<=10

这道题是道很裸的拆点最小费用流，每个点拆开后建两条边，一条费用是-a[i][j]，容量为1，另一条费用是0，容量为INF。其余的都用费用为0，容量为INF的边连接，每个点连到汇点。最后最小费用流的相反数就是答案。详见代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAX_N 55#define MAX_V 6000#define INF 1008611using namespace std;int K,N;int a[MAX_N][MAX_N];struct edge{int to,cap,cost,rev;};int V=0;vector
           
             G[MAX_V];int dist[MAX_V];int prevv[MAX_V],preve[MAX_V];void add_edge(int from,int to,int cap,int cost){ G[from].push_back((edge){to,cap,cost,G[to].size()}); G[to].push_back((edge){from,0,-cost,G[from].size()-1});}char cc;int min_cost_flow(int s,int t,int f){ int res=0; while(f>0) { fill(dist,dist+V,INF); dist[s]=0; bool update=1; while(update) { update=0; for(int v=0;v
            
             0&&dist[e.to]>dist[v]+e.cost) { //cout<<"*"<
             
              >N>>K; for(int i=0;i
              
               >a[i][j]; V=N*N*2+1; for(int i=0;i