11419 – SAM I AM ★★★★☆ 題組：Problem Set Archive with Online Judge

Presentation on theme: "11419 – SAM I AM ★★★★☆ 題組：Problem Set Archive with Online Judge"— Presentation transcript:

1 11419 – SAM I AM ★★★★☆ 題組：Problem Set Archive with Online Judge
解題者：陳仕軒、劉育錡 解題日期：2014年6月14日 題意：在方格圖上打小怪，每次可以清除一整行或一整列的小怪，問最少的步數是多少，又應該在哪些位置操作。第一行會有三個整數 R(0<R<1001)，C(0<C<1001)， N(0<N< )，R 表示方格圖的列(row)，C 表示方格圖的行(column)，N 表示有多少的敵人位置。接一來會有 N 行，每行會有兩個整數表示敵人的位置。以 R = C = N = 0 結束程式。輸入檔案大小約為 1.3 MB

2 每行測資輸出一行， 第一個印出 m  最小的砲彈數，接著用空白間隔印出砲彈位置。水平放置的砲彈使用 “r”後接一個行數(row number)，垂直“c”後接一個列數(column number)。如果有多組解，任何一組都可以通過。 題意範例： 4 4 3 1 1 1 4 3 2  2 r1 r3 4 4 2 2 2  2 r1 r2 0 0 0

3 二分圖(Bipartite graph)： 如果圖中點可以被分為兩組，並且使得所有邊都跨越組的邊界，則這就是一個二分圖。準確地說：把一個圖的頂點劃分為兩個不相交集U和V ，使得每一條邊都分別連接U、V中的頂點。 匹配（matching）：其中任意兩條邊都沒有公共頂點。例如，圖 3、圖 4 中紅色的邊就是圖 2 的匹配。 圖 3 中 1、4、5、7 為匹配點，其他頂點為未匹配點；1-5、4-7為匹配邊，其他邊為非匹配邊。

4 最大匹配：一個圖所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配。圖 4 是一個最大匹配，它包含 4 條匹配邊。 交替路：從一個未匹配點出發，依次經過非匹配邊、匹配邊、非匹配邊…形成的路徑叫交替路。 增廣路：從一個未匹配點出發，走交替路，如果途徑另一個未匹配點（出發的點不算），則這條交替路稱為增廣路（agumenting path）。例如，圖 5 中的一條增廣路如圖 6 所示： 

5 增廣路有一個重要特點：非匹配邊比匹配邊多一條。因此，研究增廣路的意義是改進匹配。只要把增廣路中的匹配邊和非匹配邊的身份交換即可。由於中間的匹配節點不存在其他相連的匹配邊，所以這樣做不會破壞匹配的性質。交換後，圖中的匹配邊數目比原來多了 1 條。 我們可以通過不停地找增廣路來增加匹配中的匹配邊和匹配點。找不到增廣路時，達到最大匹配（這是增廣路定理）。

6 解法：使用二分圖，將row當成X集合放左邊，column當成Y集合放右邊，如果在(X,Y)上有敵人，便將X和Y用線段連起來，本題是要找出最少的點覆蓋所有的邊，找出這個圖的最大匹配數即可，而找最大匹配方法，便是從左邊游上到下依序走交替路，若發現為增廣路，就將它們之間的邊狀態改變。 解法範例： 最小砲彈數： 匹配後(matching) 4 4 3 1 1 1 4   3 2 最大匹配數：2 答案： 2 r1 r3

7 最大匹配數：3 答案： 2 r1 r2 r3 Start→ ←end 完成最大匹配 這是條增廣路，所以change狀態

8 匹配後(matching) 4 4 4 1 1 1 4   3 2 2 2 最大匹配數：2 答案： 2 r1 c2
↑為什麼是c2不是r2

9 當做完最大匹配後，所有的邊分為兩類： 1. 邊的兩個端點一個是匹配點，一個不是 2
當做完最大匹配後，所有的邊分為兩類： 1. 邊的兩個端點一個是匹配點，一個不是 2. 邊的兩個端點都是匹配點 (邊的兩個端點都不是匹配點的情況是不存在的，如果存在，當前匹配則不是最大匹配) 對於未匹配點，所有與其相連的點均為覆蓋點，否則兩點的連邊就未被覆蓋，不滿足最小覆蓋的定義。 對於已經確定的覆蓋點(就是與未匹配點相連的點)u，它的匹配點(做完最大匹配後的結果)v是可以不為覆蓋點的，那與v相連的所有點都必須為覆蓋點。

10 最小覆蓋集： 做完最大匹配後，我們接著從左邊非匹配點出發走交替路，走完後輸出左邊沒被走過的點和右邊有走過的點即為答案。 X 最大匹配數：2 答案： 2 r1 c2

11 1.根據König定理，最小點覆蓋數=最大匹配數，所以我們只要找最大匹配數便是答案
討論： 1.根據König定理，最小點覆蓋數=最大匹配數，所以我們只要找最大匹配數便是答案 (證明: