#网络流，费用流#洛谷 3159 JZOJ 2765 交换棋子

本文主要是介绍#网络流，费用流#洛谷 3159 JZOJ 2765 交换棋子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给出一个黑白棋盘的起始状态，每个棋子可以向相邻或对角相邻的棋子交换，但是有限定的交换次数，问最少交换多少次到达目标状态

分析

一开始的思路就是跑费用流，
但是单纯的建图貌似不对，因为如果直接拆点会中间点交换两次，那么可以把次数取一半，对于原先是黑棋子而最后是白棋子向源点连边，原白后黑向汇点连边

代码

    #include <cstdio>#include <cstring>#include <queue>#define rr register#define id(x,y) (x-1)*m+y#define r(i,a,b) for (rr int i=a;i<=b;i++)using namespace std;const int dx[8]={0,0,1,1,1,-1,-1,-1},dy[8]={1,-1,1,0,-1,1,0,-1};struct node{int y,w,f,next;}e[8001]; bool v[805];int n,m,s,t,p[21],o[21],ls[805],tot,tot1,k=1,ans,dis[805];inline void add(int x,int y,int w,int f){e[++k]=(node){y,w,f,ls[x]}; ls[x]=k;e[++k]=(node){x,0,-f,ls[y]};ls[y]=k;}inline bool spfa(){memset(v,0,sizeof(v)); memset(dis,127/3,sizeof(dis));dis[t]=0; v[t]=1; rr deque<int>q; q.push_back(t);while (q.size()){rr int x=q.front(); q.pop_front();for (rr int i=ls[x];i;i=e[i].next)if (e[i^1].w&&dis[e[i].y]>dis[x]-e[i].f){dis[e[i].y]=dis[x]-e[i].f;if (!v[e[i].y]){v[e[i].y]=1;if (q.size()&&dis[e[i].y]<dis[q.front()]) q.push_front(e[i].y); else q.push_back(e[i].y);}}v[x]=0;}return dis[s]<707406378;}inline int dfs(int x,int now){if (x==t) {v[t]=1; return now;}rr int rest=0,f; v[x]=1;for (rr int i=ls[x];i;i=e[i].next)if (!v[e[i].y]&&e[i].w&&dis[e[i].y]+e[i].f==dis[x]){rest+=(f=dfs(e[i].y,min(e[i].w,now-rest)));if (f) ans+=f*e[i].f,e[i].w-=f,e[i^1].w+=f;if (rest==now) break;}return rest;}int main(){scanf("%d%d",&n,&m); s=n*m<<1|1; t=s+1;r(i,1,n) r(j,1,m){char c=getchar();while (c<48||c>57) c=getchar();p[i]=p[i]<<1|(c-'0'); tot+=c-'0';}r(i,1,n) r(j,1,m){char c=getchar();while (c<48||c>57) c=getchar();o[i]=o[i]<<1|(c-'0'); tot1+=c-'0';//状压}if (tot!=tot1) return !printf("-1"); tot=0;//一号剪枝，无论怎么跑都没办法r(i,1,n) r(j,1,m){char c=getchar();while (c<48||c>57) c=getchar();if ((p[i]&(1<<m-j))&&!(o[i]&(1<<m-j))) {add(s,id(i,j),1,0),tot++;if ((c-'0')&1) add(id(i,j),id(i+n,j),1,0);//如果少了1要补回去}if (!(p[i]&(1<<m-j))&&(o[i]&(1<<m-j))){add(id(i+n,j),t,1,0);if ((c-'0')&1) add(id(i,j),id(i+n,j),1,0);}add(id(i,j),id(i+n,j),(c-'0')>>1,0);r(t1,0,7){rr int x=i+dx[t1],y=j+dy[t1];if (!x||!y||x>n||y>m) continue;add(id(i+n,j),id(x,y),23333333,1);//需要交换一次}}rr int t1=0;while (spfa()){//zkw费用流do{memset(v,0,sizeof(v));t1+=dfs(s,1e9);}while (v[t]);}if (t1!=tot) return !printf("-1");//不可能else return !printf("%d",ans);}