题解

我们可以把每个格子拆成两个点，一个表示横向的，一个表示纵向的，相邻的格子横向和纵向连边。

如果直接按照题意做的话，我们应当在横向和纵向的点之间连边，有限制的边设下界为1，然后跑可行流。

或者考虑用链覆盖的思想，我们把横向点当成入点，纵向点当成出点，然后相邻的入点连向出点。

入点和出点之间连边表示的是如果流这条边，那么这个格子不放，那么有限制的格子就不连这条边。

源点连入点，出点连汇点，最大费用最大流。

代码

#include
    
     #define N 2009#define M 33#define inf 1e9using namespace std;typedef long long ll;const int xi=-2e8;queue
     
      q;int head[N],tot,he[M][M],zo[M][M],l[M][M],r[M][M],n,m,num;int dis[N],fl[N],ans,pre[N],flow;bool ex[M][M];bool vis[N];inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct edge{    int n,to,l,f;}e[N*10];inline void add(int u,int v,int l,int f){    e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;e[tot].f=f;    e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=0;e[tot].f=-f;}inline bool spfa(int s,int t){    memset(dis,-0x3f,sizeof(dis));    q.push(s);dis[s]=0;fl[s]=2e9;    while(!q.empty()){        int u=q.front();q.pop();vis[u]=0;    //    cout<
      <<" "<
       
        <
        
         xi;}inline void calc(int s,int t){    int x=t;    while(x!=s){        int i=pre[x];        e[i].l-=fl[t];e[i^1].l+=fl[t];x=e[i^1].to;    }    ans+=dis[t]*fl[t];    flow+=fl[t];}inline void solve(){    tot=1;num=0;    n=rd();m=rd();    for(int i=1;i<=n;++i)        for(int j=1;j<=m;++j)l[i][j]=++num,r[i][j]=++num;    for(int i=1;i<=n;++i)        for(int j=1;j
         
          1)add(l[i][j],r[i][j-1],1,he[i][j-1]); } else{ if(i>1)add(l[i][j],r[i-1][j],1,zo[i-1][j]); if(i