UVALive 6525 Attacking rooks 二分匹配 經典題

UVALive 6525 Attacking rooks 二分匹配 經典題

題目鏈接：點擊打開鏈接

題意：

給定n*n的棋盤，

可以在'.'上擺 象棋中的車（X是牆壁）

使得任意兩個車都不能互相攻擊到

問：最多能擺多少個車。

思路：

二分匹配

1、若沒有X，那麼做法就是 X點集為行，Y點集為列，對於圖上的每個點所在的行和列(x,y) 建一條邊 x->y

2、有了X，那麼對於每個點所在的上方能接觸到的X必須各不相同，所以給每個X標號，第一個X標記成n+1

3、這樣X點集就是行(1-n) 和 n+1-siz (siz是X的個數)

4、對於每個點，上方能接觸到的最近的X作為列，右方能接觸到的最近的Y作為行，建一條邊 X->Y

而處理每個點上方能接觸到的最近的X就是一個dp，右方也是同樣處理。

然後跑個二分匹配就好。