为何 qoj 能过的东西在洛谷 0pts

#include<bits/stdc++.h>
#define endl '\n'
#define N 2006
using namespace std;
constexpr int dx[]={0,1,0,-1},dy[]={1,0,-1,0},INF=2e9;
template <typename T,T INF>
struct MCMF_Graph {
	int tot; T maxflow,mincost;
	int cnt=2,head[N],s,t,vis[N]; T h[N],dis[N];
	struct Edge {int to,next; T w,c;} E[N],fr[N];
	MCMF_Graph(int total,int st,int ts) {tot=total,s=st,t=ts;}
	void addedge(int u,int v,T w,T c){E[cnt]={v,head[u],w,c},head[u]=cnt++;}
	void addflow(int u,int v,T w,T c){addedge(u,v,w,c),addedge(v,u,0,-c);}
	void SPFA()
	{
	    queue<int> q; q.push(s);
	    for(int i=0;i<=tot;i++)vis[i]=0,h[i]=INF;
		h[s]=0,vis[s]=1;
	    while(q.size())
	    {
	        int u=q.front(); q.pop(),vis[u]=0;
	        for(int i=head[u],v,c;i;i=E[i].next)
	        {
	            v=E[i].to,c=E[i].c;
	            if(E[i].w&&h[v]>h[u]+c) {h[v]=h[u]+c; if(!vis[v])vis[v]=1,q.push(v);}
	        }
	    }
	}
	using pTi=pair<T,int>;
	int dijkstra()
	{
	    priority_queue<pTi,vector<pTi>,greater<pTi> > q; q.push({0,s});
	    for(int i=0;i<=tot;i++)dis[i]=INF,vis[i]=0; dis[s]=0;
	    while(q.size())
	    {
	    	auto now=q.top(); int u=now.second; q.pop();
	        if(vis[u])continue; vis[u]=1;
	        for(int i=head[u],v,w;i;i=E[i].next)
	        {
	            v=E[i].to,w=h[u]-h[v]+E[i].c;
	            if(E[i].w&&dis[v]>dis[u]+w)
	            {
	                dis[v]=dis[u]+w,fr[v].next=i,fr[v].to=u;
	                if(!vis[v])q.push({dis[v],v});
	            }
	        }
	    }
	    return dis[t]<INF;
	}
	void getflow()
	{
	    SPFA();
	    while(dijkstra())
	    {
	        T fl=INF;
	        for(int i=1;i<=tot;i++)h[i]+=dis[i];
	        for(int i=t;i^s;i=fr[i].to)
	            fl=min(fl,E[fr[i].next].w);
	        for(int i=t;i^s;i=fr[i].to)
	            E[fr[i].next].w-=fl,E[fr[i].next^1].w+=fl;
	        maxflow+=fl,mincost+=fl*h[t];
	    }
	}
};
int n,m,tot,a[N][N],id[N][N];
long long sum;
pair<int,int> p[106];
struct Node {int sum,xa,ya,xb,yb;};
bool operator <(Node x,Node y) {return x.sum<y.sum;}
priority_queue<Node> q;
main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)scanf("%d",&a[i][j]),sum+=a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=0;k<2;k++)
            {
                int tx=i+dx[k],ty=j+dy[k];
                if(tx<=n&&ty<=n)
                    q.push({a[i][j]+a[tx][ty],i,j,tx,ty});
            }
    for(int i=1;i<=50&&q.size();i++)
    {
        auto [s,xa,ya,xb,yb]=q.top(); q.pop();
        if(!id[xa][ya])id[xa][ya]=++tot,p[tot]={xa,ya};
        if(!id[xb][yb])id[xb][yb]=++tot,p[tot]={xb,yb};
    }
    MCMF_Graph<int,INF> G(tot+3,tot+1,tot+2);
    int fake_s=tot+3; G.addflow(G.s,fake_s,m,0);
    for(int i=1;i<=tot;i++)
    {
        auto [x,y]=p[i];
        if((x+y)&1)G.addflow(fake_s,i,1,-a[x][y]);
        else G.addflow(i,G.t,1,-a[x][y]);
        if((x+y)&1)for(int k=0;k<4;k++)
        {
            int tx=x+dx[k],ty=y+dy[k];
            if(id[tx][ty])G.addflow(i,id[tx][ty],1,0);
        }
    }
    G.getflow(),sum+=G.mincost;
    printf("%lld\n",sum);
    return 0;
}