正題

題目鏈接:https://www.luogu.com.cn/problem/P3159

---

題目大意

$n?m$的棋盤，每個格子有黑子或白子，每次可以交換兩個位置的棋，給出起始態和最終態和每個格子參與交換的最多次數。

求最少交換次數。

---

解題思路

這里只把白色棋子算作棋子

對于一個點我們拆成3個點，$0$規定為原點，

若一個位置開始有子那么$S?(1,0)>x_0$
若一個位置最終有子那么$x_0?(1,0)>T$
若一個位置開始有子最終沒子，那么出的就比進的多1，
$x_1?(\frac{lim}{2},0)>x_0?(\frac{lim+1}{2})>x_2$
若一個位置開始沒子最終有子，那么進的就比出的多1
$x_1?(\frac{lim+1}{2},0)>x_0?(\frac{lim}{2})>x_2$
否則進的就和出的一樣多
$x_1?(\frac{lim}{2},0)>x_0?(\frac{lim}{2})>x_2$

然后費用流即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define p(x,y,z) ((x-1)*m+y+n*m*z) using namespace std; const int inf=2147483647,N=20*20*4; struct node{int to,next,w,c; }a[N*8]; const int dx[8]={1,-1,0,0,1,-1,1,-1},dy[8]={0,0,1,-1,1,-1,-1,1}; int ls[N],f[N],pre[N],mf[N],tot=1; int anscost,ansflow,n,m,s,t; char str[25]; queue<int> q; bool v[N],in[23][23],out[23][23]; void addl(int x,int y,int w,int c){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[tot].c=c;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;a[tot].c=-c; } bool SPFA(){memset(f,0x3f,sizeof(f));q.push(s);f[s]=0;mf[s]=2147483647;v[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].c<f[y]&&a[i].w){f[y]=f[x]+a[i].c;mf[y]=min(mf[x],a[i].w);pre[y]=i;if(!v[y]){v[y]=1;q.push(y);}}}v[x]=0;}return (f[t]<(2147483647/3)); } void updata(){int x=t;while(x!=s){a[pre[x]].w-=mf[t];a[pre[x]^1].w+=mf[t];x=a[pre[x]^1].to;}anscost+=f[t]*mf[t];ansflow+=mf[t]; } int main() {scanf("%d%d",&n,&m);s=p(n,m,2)+1;t=p(n,m,2)+2;int z=0,zz=0;for(int i=1;i<=n;i++){scanf("%s",str+1);for(int j=1;j<=m;j++){int x=str[j]-'0';in[i][j]=x;if(x)addl(s,p(i,j,0),1,0),zz++;}}for(int i=1;i<=n;i++){scanf("%s",str+1);for(int j=1;j<=m;j++){int x=str[j]-'0';out[i][j]=x;if(x)addl(p(i,j,0),t,1,0),z++;}}if(z!=zz){printf("-1");return 0;}for(int i=1;i<=n;i++){scanf("%s",str+1);for(int j=1;j<=m;j++){int x=str[j]-'0';if(in[i][j]&&!out[i][j]){addl(p(i,j,1),p(i,j,0),x/2,0);addl(p(i,j,0),p(i,j,2),(x+1)/2,0);}else if(!in[i][j]&&out[i][j]){addl(p(i,j,1),p(i,j,0),(x+1)/2,0);addl(p(i,j,0),p(i,j,2),x/2,0);}else{addl(p(i,j,1),p(i,j,0),x/2,0);addl(p(i,j,0),p(i,j,2),x/2,0);}for(int k=0;k<8;k++){int x=i+dx[k],y=j+dy[k];if(x<1||y<1||x>n||y>m)continue;addl(p(i,j,2),p(x,y,1),inf,1);}}}while(SPFA())updata();if(ansflow!=z) printf("-1");else printf("%d",anscost); }

總結

以上是生活随笔為你收集整理的P3159-[CQOI2012]交换棋子【费用流】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。