給你一個(gè)n*m的矩陣，每個(gè)點(diǎn)為'B'或'W'或'.'。然后你有一種碎片。碎片可以旋轉(zhuǎn)，問(wèn)可否用這種碎片精確覆蓋矩陣。N,M<=500

WB ?《==碎片

? W

題目一看，感覺(jué)是精確覆蓋（最近被覆蓋洗腦了），但是仔細(xì)分析可以知道，DLX精確覆蓋不是正解。因?yàn)镹*M=250,000遠(yuǎn)超出DLX的可行規(guī)模（數(shù)百吧，我猜）。

然后感覺(jué)是貪心或者是抑或的什么的。。。。

看了別人的代碼，發(fā)現(xiàn)是最大匹配。。。然后就想。。。。對(duì)哦=。=其實(shí)黑點(diǎn)連2個(gè)白點(diǎn)就是匹配呀。。。。

不得不說(shuō)網(wǎng)絡(luò)流構(gòu)圖還是挺有趣的，如果你會(huì)構(gòu)的話。。。。

?

首先，如果NB*2！=NW，那必然是NO，此處特判。

構(gòu)圖是這樣，每個(gè)黑點(diǎn)拆分成2個(gè)，一個(gè)只連接左右鄰接的白點(diǎn)，一個(gè)只連接上下鄰接的白點(diǎn)。然后就匹配了=。=

規(guī)模分析：250,000/3*2=166,666個(gè)黑點(diǎn)（黑點(diǎn)拆分翻倍），250,000/3*2=166,666個(gè)白點(diǎn)。邊有166,666*2=333,332條。。

?

一開(kāi)始寫(xiě)完這題是TLE...然后改了5處從>30sec變成100ms，還是有點(diǎn)收獲的。。。

①如果某一個(gè)黑點(diǎn)匹配的那個(gè)match返回0而不是1，說(shuō)明有黑點(diǎn)沒(méi)匹配到，可直接break；結(jié)果為NO。。。。>30sec ==> 27sec，TLE==>AC

②將maxn的500,000改成180,000，快了不少。。幾秒吧。。。原因應(yīng)該是多case的mesmet head

③將2個(gè)for找B字符改成統(tǒng)計(jì)時(shí)存B字符位置。。也快了些。

④將加邊的順序改成先加左（上）邊的邊，再加右（下）邊的邊。。這個(gè)從17sec變成了3sec。。。

⑤將二分匹配的vis改成int，避免多次memset。。這個(gè)從3sec變成了100ms。。。

?

第一點(diǎn)顯然的剪枝，不說(shuō)了。二三點(diǎn)好像快得也不是特別明顯，不說(shuō)了。

第四點(diǎn)，假設(shè)某行某段是WBW，那先加左邊，再加右邊的結(jié)果是B->W2->W1，也就是優(yōu)先右邊。。。這樣的話，

如果某行某段是 BWBWBWBWBWBW，那匹配的時(shí)候，每個(gè)B都只需要匹配一個(gè)就成功，不需要回溯。。。。這個(gè)的前提是順序匹配，即從1~2B

反之，如果先加右邊，再加左邊的結(jié)果是B->W1->W2，也就是優(yōu)先左邊。。。那樣的話就要回溯多次（因?yàn)檫€有列的影響）。。但如果是逆序匹配，即從2B~1，速度還是幾秒

?

第五點(diǎn)。。。應(yīng)該是最有力的改進(jìn)了。。。。傳統(tǒng)的二分匹配的vis是bool，然后匹配前memset。。因?yàn)槟切c(diǎn)一般是數(shù)百。。。

但是我們可以把vis改成int，匹配的時(shí)候把if(vis[v])continue;改成if(vis[v]==ID)continue;

二分圖最大匹配當(dāng)時(shí)學(xué)得不夠深入啊╮(╯▽╰)╭。。。。今天學(xué)習(xí)了。。。。第四點(diǎn)是SF發(fā)現(xiàn)的。。。第五點(diǎn)是參考LC他們的。。。感謝SF陪我刷了一兩頁(yè)的AC...

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 using namespace std; 11 12 #define ll long long 13 #define inf 0x3f3f3f3f 14 #define eps 1e-8 15 #define maxn 180000 16 #define maxm 360000 17 18 int vv[maxm],nxt[maxm]; 19 int head[maxn],E; 20 void init(){memset(head,-1,sizeof(head));E=0;} 21 void addedge(int u,int v){ 22 vv[E]=v,nxt[E]=head[u],head[u]=E++; 23 } 24 int pre[maxn]; 25 int vis[maxn]; 26 bool match(int x,int n,int ID){ 27 for(int i=head[x];i!=-1;i=nxt[i]){ 28 int v = vv[i]-n; 29 if(vis[v]==ID)continue; 30 vis[v] = ID; 31 if(pre[v]==-1 || match(pre[v],n,ID)){ 32 pre[v]=x; 33 return true; 34 } 35 } 36 return false; 37 } 38 bool hungary(int n){ 39 memset(pre,-1,sizeof(pre)); 40 memset(vis,0,sizeof(vis)); 41 for(int i=1;i<=n;++i) 42 if(match(i,n,i)==false)return false; 43 return true; 44 } 45 46 char ch[555][555]; 47 int idx[555][555]; 48 int bx[maxn],by[maxn]; 49 int main(){ 50 int t; 51 scanf("%d",&t); 52 while(t--){ 53 int nn,mm; 54 scanf("%d%d",&nn,&mm); 55 memset(ch,0,sizeof(ch)); 56 for(int i=1;i<=nn;++i)scanf("%s",ch[i]+1); 57 int B=0,W=0; 58 for(int i=1;i<=nn;++i)for(int j=1;j<=mm;++j) 59 if(ch[i][j]=='B')idx[i][j]=++B,bx[B]=i,by[B]=j; 60 else if(ch[i][j]=='W')idx[i][j]=++W; 61 if(B*2!=W){puts("NO");continue;} 62 init(); 63 for(int b=1;b<=B;++b){ 64 int i=bx[b],j=by[b]; 65 if(ch[i-1][j]=='W')addedge(idx[i][j],B*2+idx[i-1][j]); 66 if(ch[i+1][j]=='W')addedge(idx[i][j],B*2+idx[i+1][j]); 67 if(ch[i][j-1]=='W')addedge(idx[i][j]+B,B*2+idx[i][j-1]); 68 if(ch[i][j+1]=='W')addedge(idx[i][j]+B,B*2+idx[i][j+1]); 69 } 70 if(hungary(B<<1))puts("YES"); 71 else puts("NO"); 72 } 73 return 0; 74 } View Code

?

?

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

總結(jié)

以上是生活随笔為你收集整理的UVALive 5903 Piece it together（二分图匹配）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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