题解：
先奖每一个点裂开来
然后在见图
代码：
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=100005; int fi[N],n,t,a[55][55],cas,m,x,y,z,f[N],ne[N],num,zz[N],fl[N],gp[N],dist[N],pre[N],sl[N]; void jb(int x,int y,int z,int s) { ne[num]=fi[x]; fi[x]=num; zz[num]=y; sl[num]=z; fl[num++]=s; ne[num]=fi[y]; fi[y]=num; zz[num]=x; sl[num]=0; fl[num++]=-s; } int spfa() { memset(dist,0x3f,sizeof dist); memset(pre,-1,sizeof pre); memset(gp,0,sizeof gp); memset(f,0,sizeof f); queue<int > Q; Q.push(1); dist[1]=0; while (!Q.empty()) { int now=Q.front(); Q.pop(); f[now]=0; for (int i=fi[now];i!=-1;i=ne[i]) if (sl[i]>0) { int t=zz[i]; if (dist[t]>dist[now]+fl[i]) { dist[t]=dist[now]+fl[i]; pre[t]=now; gp[t]=i; if (!f[t]) { f[t]=1; Q.push(t); } } } } if (pre[n+2]==-1)return 1; return 0; } void Max_flow() { int cost=0,flow=0; while (!spfa()) { int f=1e9; for (int i=n+2;i>1;i=pre[i]) f=min(f,sl[gp[i]]); cost+=f; flow+=dist[n+2]*f; for (int i=n+2;i>1;i=pre[i]) { sl[gp[i]]-=f; sl[gp[i]^1]+=f; } } printf("%d ",-flow); } int main() { memset(fi,-1,sizeof fi); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { int x=(i-1)*n+j+1; int y=x+n*n; jb(x,y,1,-a[i][j]); jb(x,y,m,0); if (i<n)jb(y,x+n,m,0); if (j<n)jb(y,x+1,m,0); } jb(1,2,m,0); jb(2*n*n+1,2*n*n+2,m,0); n=2*n*n; Max_flow(); }