a274. TOI 2022/04 潛力組：防守城堡

題目描述

城堡有 M 列、N 欄。每一列的右側可以放一座砲台，每一欄的下側也可以放一座砲台，因此共有 M+N 個候選位置。

城內已經有 T 個十字陷阱。位於第 R 列、第 C 欄的陷阱啟動時，會摧毀該列與該欄上的砲台。你希望每個陷阱至多摧毀一座砲台，也就是不能同時選擇該陷阱所對應的列砲台與欄砲台。請計算最多可以放幾座砲台。

輸入格式

第一行是 M、N、T，接著 T 行各有陷阱座標 R、C。

• 1 ≤ M、N ≤ 500
• 0 ≤ T ≤ M×N
• 0 ≤ R < M，0 ≤ C < N

輸出格式

輸出最多可安裝的砲台數。

來源

TOI 2022 年 4 月潛力組〈防守城堡〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202204/Defense.pdf 題意核對鏡像：https://zerojudge.tw/ShowProblem?problemid=i179