题目描述 Description
给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= )现在从(,)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大 输入描述 Input Description
第一行两个数n,k（<=n<=, <=k<=） 接下来n行,每行n个数,分别表示矩阵的每个格子的数 输出描述 Output Description
一个数,为最大和 样例输入 Sample Input 样例输出 Sample Output 数据范围及提示 Data Size & Hint
<=n<=, <=k<=
题目
芒果君：刚学的拆点，为数不多的自己写出来的网络流……理解题意后我们发现有以下几个要点:进行K次增广路；只能向右向下走；经过格点但可以不取数。那我们可以把每个格点拆成无权和有权的两个点。从其他点（同一位置有两个）走到该点，就走到无权点，流量视为inf，费用为0；当然也可以从同一点的无权走向有权，就是取出该数，只能取一次，流量是1，费用为负点权。左上连源点，右下连汇点。套KM的板子，最后的费用取相反数就是最大价值。注意建反边的费用是正边的相反数！
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#define maxn 20010
using namespace std;
typedef long long ll;
const int inf=<<;
queue<int>Q;
int n,cnt,hl[maxn],s,t,k,vis[maxn],dis[maxn],pre[maxn],flow[maxn],id[maxn],tot;
inline int cal(int x,int y){return (x-)*n+y;}
struct Edge{
int u,v,c,f,ne,ctr;
}e[];
void add(int u,int v,int c,int f,int ctr)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].c=c;
e[cnt].f=f;
e[cnt].ctr=cnt+ctr;
e[cnt].ne=hl[u];
hl[u]=cnt;
}
bool bfs()
{
for(int i=;i<=n*n*+;++i) dis[i]=inf,pre[i]=-,vis[i]=;
dis[s]=pre[s]=;
flow[s]=inf;
Q.push(s);
while(!Q.empty()){
int x=Q.front();
Q.pop();
vis[x]=;
for(int i=hl[x];i;i=e[i].ne){
int v=e[i].v,c=e[i].c,w=e[i].f;
if(c&&dis[v]>dis[x]+w){
dis[v]=dis[x]+w;
pre[v]=x;
id[v]=i;
flow[v]=min(flow[x],c);
if(!vis[v]){
vis[v]=;
Q.push(v);
}
}
}
}
return dis[t]<inf;
}
int KM()
{
int ret();
while(bfs()){
tot++;
if(tot>k) break;
int now=t;
while(now!=s){
int i=id[now],j=e[i].ctr;
e[i].c-=flow[t];
e[j].c+=flow[t];
now=pre[now];
}
ret+=flow[t]*dis[t];
}
return ret;
}
int main()
{
int w;
scanf("%d%d",&n,&k);
for(int i=;i<=n;++i)
for(int j=;j<=n;++j){
scanf("%d",&w);
add(cal(i,j),n*n+cal(i,j),,-w,);
add(n*n+cal(i,j),cal(i,j),,w,-);
}
puts("");
for(int i=;i<=n;++i)
for(int j=;j<=n;++j){
if(j+<=n){
add(cal(i,j),cal(i,j+),inf,,);
add(cal(i,j+),cal(i,j),,,-);
add(n*n+cal(i,j),cal(i,j+),,,);
add(cal(i,j+),n*n+cal(i,j),,,-);
}
if(i+<=n){
add(cal(i,j),cal(i+,j),inf,,);
add(cal(i+,j),cal(i,j),,,-);
add(n*n+cal(i,j),cal(i+,j),,,);
add(cal(i+,j),n*n+cal(i,j),,,-);
}
}
s=,t=n*n*+;
add(,,inf,,);add(,,,,-);
add(n*n,t,inf,,);add(t,n*n,,,-);
add(t-,t,inf,,);add(t,t-,,,-);
printf("%d\n",-KM());
return ;
}