題目描述

有一個(gè)n行m列的黑白棋盤(pán)，你每次可以交換兩個(gè)相鄰格子（相鄰是指有公共邊或公共頂點(diǎn)）中的棋子，最終達(dá)到目標(biāo)狀態(tài)。要求第i行第j列的格子只能參與mi,j次交換。

輸入輸出格式

輸入格式：

?

第一行包含兩個(gè)整數(shù)n，m（1<=n, m<=20）。以下n行為初始狀態(tài)，每行為一個(gè)包含m個(gè)字符的01串，其中0表示黑色棋子，1表示白色棋子。以下n行為目標(biāo)狀態(tài)，格式同初始狀態(tài)。以下n行每行為一個(gè)包含m個(gè)0~9數(shù)字的字符串，表示每個(gè)格子參與交換的次數(shù)上限。

?

輸出格式：

?

輸出僅一行，為最小交換總次數(shù)。如果無(wú)解，輸出-1。

?

輸入輸出樣例

輸入樣例#1： 復(fù)制 3 3 110 000 001 000 110 100 222 222 222 輸出樣例#1： 復(fù)制 4

---

---

---

---

好像所有的沒(méi)有思路的題都能用毒瘤的網(wǎng)絡(luò)流來(lái)搞一下，
這題真的毒瘤，第一次見(jiàn)拆三個(gè)點(diǎn)的
看到一個(gè)點(diǎn)最多參與幾次交換，就應(yīng)該想到拆點(diǎn)限流，然后最后問(wèn)你最先的代價(jià)，應(yīng)該可以聯(lián)想到費(fèi)用這一塊，
那就向費(fèi)用流這塊搞啊，這題的建模是真的難想，所以說(shuō)就不詳細(xì)寫(xiě)了，細(xì)節(jié)挺多的。
然后就是不用擔(dān)心一個(gè)1到達(dá)目標(biāo)的時(shí)候，打亂的別的1，因?yàn)檫@時(shí)通過(guò)交換兩個(gè)點(diǎn)的先后順序來(lái)避免這個(gè)問(wèn)題。
放個(gè)網(wǎng)址： https://www.luogu.org/problemnew/solution/P3159

---

---

---

1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #define MAXN 2010 7 #define MAXM 64010 8 #define INF 0x3f3f3f3f 9 #define fpop(x) x.front();x.pop() 10 using namespace std; 11 12 int pre_node[MAXN],pre_edge[MAXN]; 13 14 char ch,mp_bg[25][25],mp_ed[25][25]; 15 16 int n,m,cnt=-1,dis[MAXN],vis[MAXN],flow[MAXN],head[MAXN],maxf[25][25]; 17 18 struct edge{ 19 int nxt,to,w,f; 20 }e[MAXM]; 21 22 inline int _bg(int x,int y){return n*m*0+(x-1)*m+y;}//起始點(diǎn)[x,y]的編號(hào) 23 inline int _ed(int x,int y){return n*m*1+(x-1)*m+y;}//目標(biāo)點(diǎn)[x,y]的編號(hào) 24 inline int _inn(int x,int y){return n*m*2+(x-1)*m+y;}//棋盤(pán)[x,y]的Inn點(diǎn)編號(hào) 25 inline int _mid(int x,int y){return n*m*3+(x-1)*m+y;}//棋盤(pán)[x,y]的mid點(diǎn)標(biāo)號(hào) 26 inline int _out(int x,int y){return n*m*4+(x-1)*m+y;}//棋盤(pán)[x,y]的Out點(diǎn)編號(hào) 27 28 inline bool in_map(int x,int y){ 29 return 1<=x && x<=n && 1<=y && y<=m; 30 }//判斷是否越界 31 32 inline void add_edge(int from,int to,int flw,int val){ 33 e[++cnt].nxt=head[from]; 34 e[cnt].to=to; 35 e[cnt].f=flw; 36 e[cnt].w=val; 37 head[from]=cnt; 38 } 39 40 queue<int>que; 41 42 inline bool spfa(int s,int t){ 43 memset(vis,0,sizeof(vis)); 44 memset(dis,0x3f,sizeof(dis)); 45 memset(flow,0x3f,sizeof(flow)); 46 que.push(s); vis[s]=true; dis[s]=0; 47 while(!que.empty()){ 48 int u=fpop(que); 49 for(int i=head[u];~i;i=e[i].nxt){ 50 int v=e[i].to; 51 if(dis[v]>dis[u]+e[i].w && e[i].f){ 52 dis[v]=dis[u]+e[i].w; 53 flow[v]=min(flow[u],e[i].f); 54 pre_node[v]=u; 55 pre_edge[v]=i; 56 vis[v]=true;que.push(v); 57 } 58 } 59 } 60 return dis[t]!=INF; 61 } 62 63 int mv[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; 64 65 int main(){ 66 memset(head,-1,sizeof(head)); 67 scanf("%d%d",&n,&m); 68 for(int i=1;i<=n;++i){ 69 for(int j=1;j<=m;++j){ 70 scanf(" %c",&mp_bg[i][j]); 71 } 72 } 73 for(int i=1;i<=n;++i){ 74 for(int j=1;j<=m;++j){ 75 scanf(" %c",&mp_ed[i][j]); 76 } 77 } 78 for(int i=1;i<=n;++i){ 79 for(int j=1;j<=m;++j){ 80 scanf(" %c",&ch); 81 maxf[i][j]=ch-'0'; 82 //最大經(jīng)過(guò)次數(shù) 83 } 84 } 85 //輸入起始態(tài)和目標(biāo)態(tài)棋盤(pán) 86 int s=0,t=n*m*5+1; 87 int cnt_1=0,cnt_2=0; 88 for(int i=1;i<=n;++i){ 89 for(int j=1;j<=m;++j){ 90 if(mp_bg[i][j]==mp_ed[i][j]){ 91 add_edge(_inn(i,j),_mid(i,j),maxf[i][j]/2,0); 92 add_edge(_mid(i,j),_inn(i,j),000000000000,0); 93 94 add_edge(_mid(i,j),_out(i,j),maxf[i][j]/2,0); 95 add_edge(_out(i,j),_mid(i,j),000000000000,0); 96 }else{ 97 if(mp_bg[i][j]=='1'){ 98 add_edge(_inn(i,j),_mid(i,j),(maxf[i][j]+0)/2,0); 99 add_edge(_mid(i,j),_inn(i,j),000000000000,0); 100 101 add_edge(_mid(i,j),_out(i,j),(maxf[i][j]+1)/2,0); 102 add_edge(_out(i,j),_mid(i,j),000000000000,0); 103 } 104 if(mp_ed[i][j]=='1'){ 105 add_edge(_inn(i,j),_mid(i,j),(maxf[i][j]+1)/2,0); 106 add_edge(_mid(i,j),_inn(i,j),000000000000,0); 107 108 add_edge(_mid(i,j),_out(i,j),(maxf[i][j]+0)/2,0); 109 add_edge(_out(i,j),_mid(i,j),000000000000,0); 110 } 111 } 112 113 if(mp_bg[i][j]=='1'){ 114 ++cnt_1; 115 //連接源點(diǎn)到初始點(diǎn) f=1 w=0; 116 add_edge(s,_mid(i,j),1,0); 117 add_edge(_mid(i,j),s,0,0); 118 //連接起始點(diǎn)到棋盤(pán) 119 // add_edge(_bg(i,j),_mid(i,j),1,0); 120 // add_edge(_mid(i,j),_bg(i,j),0,0); 121 } 122 if(mp_ed[i][j]=='1'){ 123 ++cnt_2; 124 //連接終結(jié)點(diǎn)到匯點(diǎn) f=1 w=0; 125 add_edge(_mid(i,j),t,1,0); 126 add_edge(t,_mid(i,j),0,0); 127 //連接棋盤(pán)到終結(jié)點(diǎn) 128 // add_edge(_mid(i,j),_ed(i,j),1,0); 129 // add_edge(_ed(i,j),_mid(i,j),0,0); 130 } 131 //棋盤(pán)的八連通邊 f=INF w=1; 132 for(int k=0;k<8;++k){ 133 int ni=i+mv[k][0]; 134 int nj=j+mv[k][1]; 135 if(in_map(ni,nj)){ 136 //從點(diǎn)[i,j]的out連接點(diǎn)[ni,nj]的inn 137 add_edge(_out(i,j),_inn(ni,nj),INF,+1); 138 add_edge(_inn(ni,nj),_out(i,j),000,-1); 139 } 140 } 141 } 142 } 143 //棋子數(shù)變動(dòng)->No solution 144 if(cnt_1!=cnt_2){ 145 puts("-1"); 146 return 0; 147 } 148 //然后跑費(fèi)用流 149 int max_flow=0,min_cost=0; 150 while(spfa(s,t)){ 151 max_flow+=flow[t]; 152 min_cost+=flow[t]*dis[t]; 153 int u=t; 154 while(u!=s){ 155 e[pre_edge[u]^0].f-=flow[t]; 156 e[pre_edge[u]^1].f+=flow[t]; 157 u=pre_node[u]; 158 } 159 } 160 if(max_flow!=cnt_1){ 161 puts("-1"); 162 return 0; 163 } 164 printf("%d\n",min_cost); 165 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhangbuang/p/10638102.html

總結(jié)

以上是生活随笔為你收集整理的P3159 [CQOI2012]交换棋子（费用流）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。