明显超出我能力范围。
只放题解。
再放代码。
#include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cctype> #include<queue> #define maxn 100200 using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } int n,m; inline int calc(int x,int y,int z){ return (x-1)*m+y+(z-1)*(n*m); } inline int count(int i){ return i&1?i+1:i-1; } struct Edge{ int from,next,to,dis,val,flow; }edge[maxn]; int head[maxn],num; inline void addedge(int from,int to,int dis,int val){ edge[++num]=(Edge){from,head[from],to,dis,val,0}; head[from]=num; } inline void add(int from,int to,int dis,int val){ addedge(from,to,dis,val); addedge(to,from,-dis,0); } bool sta[100][100]; bool edn[100][100]; int swa[100][100]; int Start,End; int u[9]={0,0,1,1,1,0,-1,-1,-1}; int w[9]={0,1,1,0,-1,-1,-1,0,1}; struct Ans{ long long dis,val; Ans(){dis=val=0;} }; long long dis[maxn]; long long pre[maxn]; int flow[maxn]; bool vis[maxn]; int sum; Ans spfa(){ Ans ans; memset(dis,127/3,sizeof(dis)); long long Max=dis[0]; dis[Start]=0; flow[Start]=0x7fffffff; queue<int>q; q.push(Start); while(!q.empty()){ int from=q.front();q.pop();vis[from]=0; for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(edge[i].dis+dis[from]>=dis[to]||edge[i].val==edge[i].flow) continue; dis[to]=dis[from]+edge[i].dis; pre[to]=i; flow[to]=min(flow[from],edge[i].val-edge[i].flow); if(!vis[to]){ vis[to]=1; q.push(to); } } } if(dis[End]==Max) return ans; long long now=End; ans.val=flow[End]; ans.dis=dis[End]; sum+=flow[End]; while(now!=Start){ long long ret=pre[now]; edge[ret].flow+=flow[End]; edge[count(ret)].flow-=flow[End]; now=edge[ret].from; } return ans; } int main(){ n=read(),m=read(); End=calc(n,m,3)+1; for(int i=1;i<=n;++i){ char ch[100]; scanf("%s",ch+1); for(int j=1;j<=m;++j) sta[i][j]=ch[j]-'0'; } for(int i=1;i<=n;++i){ char ch[100]; scanf("%s",ch+1); for(int j=1;j<=m;++j) edn[i][j]=ch[j]-'0'; } for(int i=1;i<=n;++i){ char ch[100]; scanf("%s",ch+1); for(int j=1;j<=m;++j) swa[i][j]=ch[j]-'0'; } int sum1=0,sum2=0; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ if(sta[i][j]){ sum1++; add(Start,calc(i,j,2),0,1); } if(edn[i][j]){ sum2++; add(calc(i,j,2),End,0,1); } if(sta[i][j]&&(!edn[i][j])){ add(calc(i,j,1),calc(i,j,2),1,swa[i][j]>>1); add(calc(i,j,2),calc(i,j,3),0,(swa[i][j]+1)>>1); } if((!sta[i][j])&&edn[i][j]){ add(calc(i,j,1),calc(i,j,2),1,(swa[i][j]+1)>>1); add(calc(i,j,2),calc(i,j,3),0,swa[i][j]>>1); } if(sta[i][j]==edn[i][j]){ add(calc(i,j,1),calc(i,j,2),1,swa[i][j]>>1); add(calc(i,j,2),calc(i,j,3),0,swa[i][j]>>1); } for(int k=1;k<9;++k){ int x=i+u[k];int y=j+w[k]; if(x<1||x>n||y<1||y>m) continue; add(calc(i,j,3),calc(x,y,1),0,0x7fffffff); } } if(sum1!=sum2){ printf("-1"); return 0; } int ans=0; while(1){ Ans now=spfa(); if(!now.val) break; ans+=now.val*now.dis; } if(sum!=sum1){ printf("-1"); return 0; } printf("%d",ans); return 0; }
https://www.luogu.org/problemnew/solution/P3159