P2045 方格取数加强版

#include<cstdio>
#define re register 
#define inf 2147483647
#define mod 10000
int S,T,n,k,em=1,e[100001],flow[100001],pre[100001],cost[100001],last[100001],next[100001],cur[100001];
int ans,f[55][55],q[100001],dis[100001];
bool bz[100001];
inline int max(re int a,re int b){return a>b?a:b;}
inline int min(re int a,re int b){return a<b?a:b;}
bool bfs()
{
	re int i,l=0,r=1,j,p;
	for(i=1;i<=2*n*n+1;++i)dis[i]=-1;
	dis[0]=0,q[r]=0,bz[0]=1;
	while(l<r)
	{
		l=l%mod+1;
		j=q[l];
		bz[j]=0;
		for(i=last[j];i;i=next[i])
		{
			p=e[i];
			if(flow[i]&&dis[p]<dis[j]+cost[i])
			{
				dis[p]=dis[j]+cost[i];
				if(!bz[p])
				{
					r=r%mod+1;
					q[r]=p;
					bz[p]=1;
				}
			}
		}
	}
	return dis[n*n+1]!=-1;
}
int dfs(re int x,re int p)
{
	if(x==T||!p)return p;
	re int i,j,l,sum=0;
	
	for(i=cur[x];i;i=next[i])
	{
		cur[x]=next[i];
		j=e[i];
		if(dis[j]==dis[x]+cost[i])
		{
			l=dfs(j,min(flow[i],p));
			flow[i]-=l,sum+=l,flow[i^1]+=l,p-=l,ans+=cost[i];
		}
		if(!p)break;
	}
	return sum;
}
void add(re int u,re int v,re int d,re int c)
{
	e[++em]=v;
	next[em]=last[u];
	last[u]=em;
	flow[em]=d;
	cost[em]=c;
	e[++em]=u;
	next[em]=last[v];
	last[v]=em;
	flow[em]=0;
	cost[em]=-c;
}
int main()
{
	re int i,j,p,l;
	scanf("%d%d",&n,&k);
	S=0,T=n*n+1;
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=n;++j)
		{
			scanf("%d",&f[i][j]);
			p=(i-1)*n+j;
			add(p,p+T,1,f[i][j]);
			if(j<n)
			{
				add(p,p+1,inf,0);
				add(p+T,p+1,inf,0);
			}
			if(i<n)
			{
				add(p,p+n,inf,0);
				add(p+T,p+n,inf,0);
			}
		}
	}
	add(S,1,k,0);
	add(n*n,T,inf,0);
	add(n*n+T,T,k,0);
	while(bfs())
	{
		for(j=0;j<=2*n*n+1;++j)cur[j]=last[j];
		j=dfs(0,1);
		
	}
	printf("%d",ans);
}
/*
3 2
1 2 3
0 2 1
1 4 2
*/

10分求助，调了一晚上只有十分QAQ