匈牙利算法-二分圖 最小覆蓋

1、POJ 3041: AsteroidsKönig定理與匈牙利算法 題目大意：在一片由N * N（1 N 500）的方格陣表示的宇宙空間里，有些格子里面有一些小行星（Asteroid），小行星共有K（1 K 10,000）個(gè)。Bessie要在這個(gè)地區(qū)航行，它就需要消滅所有的小行星。Bessie有一種被稱作“applepi破壞光線”的超級武器。正如這個(gè)威武的名字一樣，發(fā)動(dòng)一次就可以破壞一行或者一列里面所有的小行星。由于“applepi破壞光線”的彈藥是很貴的，Bessie決定節(jié)儉地使用這種武器。你需要計(jì)算它至少需要使用多少次“applepi破壞光線”。好吧，我承認(rèn)那個(gè)名字是我YY的，大家

2、無視好了另外，由于匈牙利算法又基礎(chǔ)又難以說清，請不懂的同學(xué)們自行查找資料閱讀，看明白之后還是挺簡單的。推薦百度文庫里面的資料（傳送門），過一陣子我也會(huì)考慮自己寫一個(gè)教程。匈牙利算法是尋找最大匹配的優(yōu)秀算法，那么與這個(gè)看上去一點(diǎn)也不像二分圖的題來說有什么用處呢？讓我們來做一個(gè)嘗試：把樣例數(shù)據(jù)里面的橫坐標(biāo)作為二分圖的一部，縱坐標(biāo)作為二分圖的另一部，坐標(biāo)為(x, y)的小行星表示為從橫坐標(biāo)x到縱坐標(biāo)y的一段弧，就有了下圖：可以看出，原問題變成了下面這個(gè)問題：給定一個(gè)二分圖G = (V, E)，定義一個(gè)點(diǎn)如果被覆蓋，那么稱所有與這個(gè)點(diǎn)相鄰的弧被覆蓋。求出最少需要覆蓋多少個(gè)點(diǎn)才能覆蓋所有的邊。如上兩個(gè)圖

3、，原問題中在x = 1和y = 2兩處使用超級武器，等價(jià)于在右圖中覆蓋左邊的點(diǎn)1和右邊的點(diǎn)2。我們稱這個(gè)問題的答案為最小覆蓋數(shù)P，顯然在樣例中P = 2?，F(xiàn)在我們給出結(jié)論，若將二分圖最大匹配的邊集設(shè)為M，則P = | M |。也就是最大匹配數(shù)。證明如下：首先證明P | M | 。對于M中的每一條邊，它們都不相鄰。那么至少需要覆蓋 | M | 個(gè)點(diǎn)才能覆蓋M中的所有邊。故有P | M | ?，F(xiàn)在給出一種令P = | M |的覆蓋方法。如果當(dāng)前圖中對于所有的v V，都有v M，顯然有P = | M |。否則，任取一條邊v0，使v0 V且v0 M。那么顯然v0的兩個(gè)端點(diǎn)至少有一個(gè)被匹配。如果有一端被

4、匹配，設(shè)這個(gè)端點(diǎn)為a0。首先覆蓋a0，然后觀察與a0匹配的點(diǎn)a1的狀況。如果存在與a1相鄰的邊v1，滿足v1 V且v1 M，則v1一定不與沒有匹配過的點(diǎn)相鄰，否則，v0，v(a0, a1)及v1就形成了增廣路?，F(xiàn)在繼續(xù)覆蓋與v1相鄰的另外一個(gè)點(diǎn)a2，然后依次操作，直到新連接到的匹配過的點(diǎn)不與V M中的邊相鄰為止。如果兩端都被匹配，就向兩個(gè)方向進(jìn)行同樣的操作。從v0的一系列操作結(jié)束之后，考察還沒有被覆蓋的邊，繼續(xù)進(jìn)行操作。這樣最后所有的邊一定會(huì)被全部覆蓋。如果說有沒有被覆蓋到的邊，這條邊不可能同時(shí)與兩個(gè)匹配過的點(diǎn)相鄰。如果這樣，在剛才的過程中一定會(huì)檢索到這條邊。所以說它必然是與一個(gè)匹配過的點(diǎn)ax

5、相鄰，與一個(gè)沒有匹配過的點(diǎn)ar相鄰，并且ax的匹配點(diǎn)ay一定被覆蓋過。那么，從ay向上找尋剛才的過程遍歷過的邊，與最后的v(ax, ar)一定會(huì)形成一條增廣路，矛盾。觀察到每條M中的邊都有且僅有一個(gè)端點(diǎn)被覆蓋，所以說P = | M |。由于P | M | 且存在P = | M |的狀況，故P = | M | ，證明完畢。也就是說，這個(gè)題只需要用匈牙利算法求出最大匹配數(shù)就可以了。那么代碼如下：#include <stdio.h>#define FREE -1/* POJ 3041: Asteroids */typedef struct str_vec   

6、; int to;    struct str_vec *next; vector;vector chain510;char sch510;int dual510;int ask (int x, int y)    int tar, cur;    vector *p;    if (dualy = FREE) dualy = x; return 1;     else       &#

7、160;    tar = dualy; schy = 1;        for (p = (chain + tar)->next; p != NULL; p = p->next)                    cur = p->to;    

8、0;       if (schcur) continue;            else if (ask(tar, cur) dualy = x; return 1;                 schy = 0; return 0;    int m

9、ain ()    int n, k, x, y, i, j, cur, ans = 0;    vector *p, *r;    scanf("%d %d", &n, &k);    for (i = 0; i < n; i+)            chaini.to = i;    

10、60;   chaini.next = NULL;            memset(dual, FREE, sizeof(dual);    for (i = 0; i < k; i+)            scanf("%d %d", &x, &y);     

11、;   x-, y-;        r = chain + x;        while (r->next != NULL) r = r->next;        p = (vector *)malloc(sizeof(vector);        p->to = y, p

12、->next = NULL; r->next = p;            for (i = 0; i < n; i+)            p = (chain + i)->next;        while (p != NULL)      &#

13、160;             memset(sch, 0, sizeof(sch);            cur = p->to;            if (ask(i, cur) ans+; break;             p = p->next;                    printf(&q