解题思路
神仙题。调了一个晚上+半个上午。。这道咋看咋都不像图论的题竟然用费用流做，将行+列为奇数的点和偶数的点分开，也就是匹配问题，然后把一个点复制四份，分别代表这个点的上下左右接头，如果有这个接头就加一个费用为(0)，流量为(1)的边，如果没有要分情况讨论，因为从源点到这个点的流量是固定的，当只有一个接头时，可以让这个点向自己其余三个点连费用为(1)，流量为(1)的边，当有两个接头并且两个接头相邻时，让这个点的两个接头分别与对应的方向连边，当有三个接头时，让那个没有的接头向相邻的连费用为(1)的边，向相对的连费用为(2)的边。然后一边费用流就行了。代码比较丑。建图写挫了。。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
using namespace std;
const int MAXN = 10005;
const int MAXM = 100005;
const int inf = 0x3f3f3f3f;
const int zz[4] = {1,2,4,8}; // 0 1 2 3
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='0'?0:1,ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return f?x:-x;
}
int n,m,head[MAXN],to[MAXM<<1],nxt[MAXM<<1],val[MAXM<<1],cost[MAXM<<1],pre[MAXN];
int S,T,cnt=1,maxflow,ans,dis[MAXN],ch[MAXN][5],num,tot,sum,pos[2005][2005];
int incf[MAXN],all;
bool vis[MAXN];
queue<int> Q;
inline void add(int bg,int ed,int z,int w){
to[++cnt]=ed,nxt[cnt]=head[bg],val[cnt]=z,cost[cnt]=w,head[bg]=cnt;
}
inline void solve1(int p,int x,int op){
for(int i=0;i<=3;i++)
if((x&zz[i])) {
if(op&1) add(p,ch[p][i],1,0),add(ch[p][i],p,0,0);
else add(ch[p][i],p,1,0),add(p,ch[p][i],0,0);
if(i<2) {
if(op&1) add(p,ch[p][i+2],1,2),add(ch[p][i+2],p,0,-2);
else add(ch[p][i+2],p,1,2),add(p,ch[p][i+2],0,-2);
}
else {
if(op&1) add(p,ch[p][i-2],1,2),add(ch[p][i-2],p,0,-2);
else add(ch[p][i-2],p,1,2),add(p,ch[p][i-2],0,-2);
}
if(op&1){
add(p,ch[p][(i+1)%4],1,1),add(ch[p][(i+1)%4],p,0,-1);
add(p,ch[p][(i+3)%4],1,1),add(ch[p][(i+3)%4],p,0,-1);
}
else{
add(ch[p][(i+1)%4],p,1,1),add(p,ch[p][(i+1)%4],0,-1);
add(ch[p][(i+3)%4],p,1,1),add(p,ch[p][(i+3)%4],0,-1);
}
}
}
inline void solve2(int p,int x,int op){
if(x==5 || x==10){
for(int i=0;i<=3;i++)
if(x&zz[i]){
if(op&1) add(p,ch[p][i],1,0),add(ch[p][i],p,0,0);
else add(ch[p][i],p,1,0),add(p,ch[p][i],0,0);
}
return ;
}
for(int i=0;i<=3;i++){
if(x&zz[i]){
if(op&1) add(p,ch[p][i],1,0),add(ch[p][i],p,0,0);
else add(ch[p][i],p,1,0),add(p,ch[p][i],0,0);
}
else{
if(i<2) {
if((op&1))
add(ch[p][i+2],ch[p][i],1,1),add(ch[p][i],ch[p][i+2],0,-1);
else
add(ch[p][i],ch[p][i+2],1,1),add(ch[p][i+2],ch[p][i],0,-1);
}
else {
if((op&1))
add(ch[p][i-2],ch[p][i],1,1),add(ch[p][i],ch[p][i-2],0,-1);
else
add(ch[p][i],ch[p][i-2],1,1),add(ch[p][i-2],ch[p][i],0,-1);
}
}
}
}
inline void solve3(int p,int x,int op){
for(int i=0;i<=3;i++){
if(x&zz[i]){
if(op&1) add(p,ch[p][i],1,0),add(ch[p][i],p,0,0);
else add(ch[p][i],p,1,0),add(p,ch[p][i],0,0);
}
else {
if((op&1)){
add(ch[p][(i+1)%4],ch[p][i],1,1);
add(ch[p][i],ch[p][(i+1)%4],0,-1);
add(ch[p][(i+3)%4],ch[p][i],1,1);
add(ch[p][i],ch[p][(i+3)%4],0,-1);
if(i<2) {
add(ch[p][i+2],ch[p][i],1,2);
add(ch[p][i],ch[p][i+2],0,-2);
}
else {
add(ch[p][i-2],ch[p][i],1,2);
add(ch[p][i],ch[p][i-2],0,-2);
}
}
else{
add(ch[p][i],ch[p][(i+1)%4],1,1);
add(ch[p][(i+1)%4],ch[p][i],0,-1);
add(ch[p][i],ch[p][(i+3)%4],1,1);
add(ch[p][(i+3)%4],ch[p][i],0,-1);
if(i<2) {
add(ch[p][i],ch[p][i+2],1,2);
add(ch[p][i+2],ch[p][i],0,-2);
}
else {
add(ch[p][i],ch[p][i-2],1,2);
add(ch[p][i-2],ch[p][i],0,-2);
}
}
}
}
}
inline void solve4(int p,int op){
for(int i=0;i<=3;i++){
if(op&1) add(p,ch[p][i],1,0),add(ch[p][i],p,0,0);
else add(ch[p][i],p,1,0),add(p,ch[p][i],0,0);
}
}
bool spfa(){
while(Q.size()) Q.pop();
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
vis[S]=1;dis[S]=0;incf[S]=inf;Q.push(S);
while(Q.size()){
int x=Q.front();Q.pop();vis[x]=0;
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(dis[u]>cost[i]+dis[x] && val[i]) {
dis[u]=cost[i]+dis[x];
incf[u]=min(incf[x],val[i]);
pre[u]=i;
if(!vis[u]) vis[u]=1,Q.push(u);
}
}
}
return (dis[T]==inf)?false:true;
}
inline void update(){
int x=T,i;
while(x!=S){
i=pre[x];
val[i]-=incf[T];
val[i^1]+=incf[T];
x=to[i^1];
}
maxflow+=incf[T];
ans+=incf[T]*dis[T];
}
int main(){
n=rd(),m=rd();S=++num;T=++num;int x,p;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
x=rd();p=++num;pos[i][j]=p;
for(int k=0;k<=3;k++) ch[p][k]=++num;
tot=__builtin_popcount(x);
if((i+j)&1) add(S,p,tot,0),add(p,S,0,0);
else add(p,T,tot,0),add(T,p,0,0);
if(tot==1) solve1(p,x,i+j);
else if(tot==2) solve2(p,x,i+j);
else if(tot==3) solve3(p,x,i+j);
else solve4(p,i+j);
sum+=tot;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(!((i+j)&1)) continue;
if(i!=1){
add(ch[pos[i][j]][0],ch[pos[i-1][j]][2],1,0);
add(ch[pos[i-1][j]][2],ch[pos[i][j]][0],0,0);
}
if(j!=1){
add(ch[pos[i][j]][3],ch[pos[i][j-1]][1],1,0);
add(ch[pos[i][j-1]][1],ch[pos[i][j]][3],0,0);
}
if(i!=n){
add(ch[pos[i][j]][2],ch[pos[i+1][j]][0],1,0);
add(ch[pos[i+1][j]][0],ch[pos[i][j]][2],0,0);
}
if(j!=m){
add(ch[pos[i][j]][1],ch[pos[i][j+1]][3],1,0);
add(ch[pos[i][j+1]][3],ch[pos[i][j]][1],0,0);
}
}
if(sum&1) {puts("-1");return 0;}
sum>>=1;
while(spfa()) update();
if(maxflow!=sum) puts("-1");
else printf("%d
",ans);
return 0;
}