i179: 防守城堡 (Defense)
Tags : flow 二分圖匹配 匈牙利算法 圖論
Accepted rate : 3人/6人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-05 20:19

Content

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

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

Input

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

範圍限制:

$\color{black}{1 ≤ M, N ≤ 500,0 ≤ T ≤ MN}$

$\color{black}{0 ≤ R ≤ M–1,\ \ 0 ≤ C ≤ N–1}$ 

Output

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

Sample Input #1
3 3 5
0 0
0 2
1 1
2 0
2 2
Sample Output #1
3
Sample Input #2
4 2 3
0 0
1 1
2 0
Sample Output #2
4
測資資訊:
記憶體限制: 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
Hint :

第一組(測資點$\color{black}{00}$ ~ $\color{black}{01}$):$\color{black}{N = 2}$。

第二組(測資點$\color{black}{02}$ ~ $\color{black}{07}$):$\color{black}{M ≤ 10, N ≤ 10}$。

第三組(測資點$\color{black}{08}$ ~ $\color{black}{19}$):限制如輸入格式。

Tags:
flow 二分圖匹配 匈牙利算法 圖論
出處:
TOI練習賽202204潛力組第3題 [管理者:
linlincaleb@... (臨末之頌)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」