【正文】 2 3 4 5 1 2 3 4 把每個橫向塊看作 X部的點，豎向塊看作 Y部的點，若兩個塊有公共的空地，則在它們之間連邊。 ?理清一個關(guān)系：最小路徑覆蓋數(shù)＝ G的定點數(shù)－最小路徑覆蓋中的邊數(shù) 例題 4 最小路徑覆蓋 ?試想我們應(yīng)該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個頂點相交。 ?該二分圖的最大匹配數(shù)則是最少要打的槍數(shù)。因此，我們很自然想到了下面這種簡單的模型： 以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖： 這是 NP問題！ 我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“ 塊 ” 。 ?數(shù)學(xué)模型： G是加權(quán)完全二分圖，求總權(quán)值最大的完備匹配。 j := father[t]。 匈牙利算法 ?用增廣路求最大匹配 (稱作匈牙利算法，匈牙利數(shù)學(xué)家 Edmonds于 1965年提出 ) ?算法輪廓： ? (1)置 M為空 ? (2)找出一條增廣路徑 P，通過取反操作獲得更大的匹配 M’代替 M ? (3)重復(fù) (2)操作直到找不出增廣路徑為止 匈牙利算法 ?程序清單： ? Function find(k:integer):integer。如頂點集 V可分割為兩個互不相交的子集，并且圖中每條邊依附的兩個頂點都分屬兩個不同的子集。 sf := 1。 ? end。 KM算法 ?修改方法如下： ?先將一個未被匹配的頂點 u(u in {x})做一次增廣路，記下哪些結(jié)點被訪問那些結(jié)點沒有被訪問。 于是，問題轉(zhuǎn)化成這樣的一個二部圖： 1 1 2 2 3 3 4 4 5 由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問題轉(zhuǎn)化為二部圖的最大匹配問題。 ?拆點：將每一個頂點 i拆成兩個頂點 Xi和 Yi。問至少打幾槍，才能打光所有的鳥？ ?建圖：二分圖的 X部為每一行， Y部為每一列，如果 (i,j)有一只鳥，那么連接 X部的 i與 Y部的 j。因此，我們很自然想到了下面這種簡單的模型： 以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖： 例題 1 Place the Robots（ ZOJ） 模型一 5 4 6 7 8 3 2 1 1 2