没有题解。
转化成要尽量少的格子是直的，然后就和这道题一样了：here
代码：
#include<bits/stdc++.h> #define ll long long #define re register #define cs const namespace IO{ inline char gc(){ static cs int Rlen=1<<22|1; static char buf[Rlen],*p1,*p2; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; } template<typename T>inline T get(){ char c;T num; while(!isdigit(c=gc()));num=c^48; while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48); return num; }inline int gi(){return get<int>();} } using namespace IO; using std::cerr; using std::cout; cs int R=155,C=35; int S,T,tot; namespace NetWork{ cs int N=(R*C+100)<<1|7; struct edge{int to,rev,cap,w;}; typedef std::vector<edge>::iterator iter; std::vector<edge> G[N];iter cur[N]; inline void adde(int u,int v,int cap,int cost){ G[u].push_back((edge){v,(int)G[v].size(),cap,cost}); G[v].push_back((edge){u,(int)G[u].size()-1,0,-cost}); } int dis[N],vis[N]; inline bool SPFA(){ memset(dis+1,0x3f,tot<<2); std::deque<int> q;q.push_back(S),dis[S]=0; while(!q.empty()){ int u=q.front();q.pop_front(); vis[u]=false,cur[u]=G[u].begin(); for(iter e=G[u].begin();e!=G[u].end();++e) if(e->cap&&dis[e->to]>dis[u]+e->w){ dis[e->to]=dis[u]+e->w; if(!vis[e->to]){ if(!q.empty()&&dis[e->to]<dis[q.front()])q.push_front(e->to); else q.push_back(e->to); vis[e->to]=true; } } }return dis[T]<1e9; } int tot_flow,tot_cost; int dfs(int u,int flow){ if(u==T){ tot_flow+=flow; tot_cost+=dis[T]*flow; return flow; }int ans=0;vis[u]=true; for(iter &e=cur[u];e!=G[u].end();++e) if(e->cap&&dis[e->to]==dis[u]+e->w&&!vis[e->to]){ int delta=dfs(e->to,std::min(flow-ans,e->cap)); ans+=delta,e->cap-=delta,G[e->to][e->rev].cap+=delta; }vis[u]=false;return ans; } void Flow(){ tot_cost=tot_flow=0; while(SPFA())dfs(S,1e9); } } using NetWork::adde; using NetWork::tot_flow; using NetWork::tot_cost; int n,m,ct,cnt,ans; int id1[R][C],id2[R][C]; int ok[R][C],val[R][C]; #undef zxyoi signed main(){ #ifdef zxyoi freopen("project.in","r",stdin); #else #ifndef ONLINE_JUDGE freopen("project.in","r",stdin);freopen("project.out","w",stdout); #endif #endif n=gi(),m=gi();S=1,T=tot=2; for(int re i=1;i<=n;++i) for(int re j=1;j<=m;++j){ ok[i][j]=gi()^1; if(ok[i][j])id1[i][j]=++tot,id2[i][j]=++tot; } for(int re i=1;i<=n;++i) for(int re j=1;j<=m;++j){ val[i][j]=gi(); if(ok[i][j]){ ans+=val[i][j];++cnt; if((i^j)&1){ ++ct; adde(id1[i][j],T,1,0); adde(id2[i][j],T,1,0); }else { --ct; adde(S,id1[i][j],1,0); adde(S,id2[i][j],1,0); for(int re k=0;k<4;++k){ static cs int dx[]={0,1,0,-1}; static cs int dy[]={1,0,-1,0}; int x=i+dx[k],y=j+dy[k]; if(x<1||x>n||y<1||y>m||!ok[x][y])continue; if(k&1)adde(id1[i][j],id2[x][y],1,0); else adde(id2[i][j],id1[x][y],1,0); } } adde(id1[i][j],id2[i][j],1,val[i][j]); adde(id2[i][j],id1[i][j],1,val[i][j]); } } if(ct)return puts("-1"),0;NetWork::Flow(); if(tot_flow!=cnt)return puts("-1"),0; cout<<ans-tot_cost<<"\n"; return 0; }