i179. 防守城堡 (Defense) - 高中生程式解題系統

內容

小東最近迷上一款戰略遊戲，在這個遊戲中你可以建造屬於自己的莊園，進攻並佔領他人的城堡掠奪資源；也可以設下守備避免他人攻擊自己的城堡。由於系統告訴小東有人要進攻他的城堡了，他開始部屬防禦。這個遊戲中的城堡可以被視為大小為 $M \times N$ 的矩形，敵人的士兵會從城堡某一直行的下方往上朝向城堡進攻，或者從某一橫列的右方往左朝向城堡進攻；而玩家可以在城堡每一直行的最下方，以及每一橫列的最右方城牆上設置一座防禦砲台，或者是在城內設置十字陷阱以抵禦攻擊（如下圖）。雖然小東的城堡已經安裝了一些十字陷阱，但在上次整修之後還沒有安裝任何一座砲台，因此小東想把所有的預算花在安裝砲台上。

由於十字陷阱非常強大，在發動時會摧毀所在位置整橫列與直行的東西（如上圖灰底的區域），包含自己所建的砲台也會一併被摧毀，因此小東希望不要有兩座砲台同時落在同一個十字陷阱所在的橫列與直行，也就是當一個十字陷阱發動時最多只會有一座砲台被摧毀。但是為了盡可能的抵擋敵人的攻擊，小東希望砲台的數量越多越好。請你幫忙計算小東最多可以安裝多少座砲台。

輸入說明

第一列有三個整數 $M$ 、 $N$ 、 $T$ 代表城堡的大小以及城堡內已安裝的十字陷阱的個數。接下來有 $T$ 列每一列包含兩個整數 $R$ 、 $C$ ，代表十字陷阱位在城堡的哪一列哪一行。

範圍限制:

$1 \leq M, N \leq 500 ， 0 \leq T \leq M N$

$0 \leq R \leq M - 1, 0 \leq C \leq N - 1$

輸出說明

請輸出一個數字，代表小東最多可以安裝多少座砲台。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1K
公開測資點#15 (5%): 1.0s , <1K
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <10M

提示：

第一組（測資點 $00$ ~ $01$ ）： $N = 2$ 。

第二組（測資點 $02$ ~ $07$ ）： $M \leq 10, N \leq 10$ 。

第三組（測資點 $08$ ~ $19$ ）：限制如輸入格式。

標籤:

flow 二分圖匹配匈牙利算法圖論

出處:

TOI練習賽202204 潛力組第3題 [管理者： linlincaleb@gmail.com

linlincaleb@ ... (臨末之頌) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」