POJ 1496 C++ （圖論）

//匈牙利算法實(shí)現(xiàn)二分圖的最大匹配，較最大流實(shí)現(xiàn)來的簡單些
//特點(diǎn)不需要建模，原理還是樸素最大流原理，尋找增廣路徑用DFS,如找到一條增廣路徑，沿路邊取反

#include<iostream>
using namespace std;
int n,m,res;
int l[300],r[300],map[300][300],used[300];

bool path(int u)
{int v;
for(v=0;v<m;v++)
     if(map[u][v] && !used[v])
       {used[v]=1;
        if(r[v]==-1 || path(r[v]))
           {  l[u]=v;
              r[v]=u;
              return true;
           }
       }
   return false;        
}

void solve()
{ int i;
  memset(l,-1,sizeof(l));
  memset(r,-1,sizeof(r));
  for(i=0;i<n;i++)
       if(l[i]==-1)
           {  memset(used,0,sizeof(used));
              if(path(i))
                 res++;
            }  

}

int main()
{ int Case,i,j,k,temp;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
  scanf("%d",&Case);
  while(Case--)
       { memset(map,0,sizeof(map));
         scanf("%d%d",&n,&m);
         for(i=0;i<n;i++)
             { scanf("%d",&k);
               for(j=0;j<k;j++)
                   {scanf("%d",&temp);
                    map[i][temp-1]=1;
                   }
               }
           res=0;    
           solve();
           if(res==n)
              printf("YES\n");
           else
             printf("NO\n");            
         }
   return 0;      
}              




什么是二分圖，什么是二分圖的最大匹配，這些定義我就不講了，網(wǎng)上隨便都找得到。二分圖的最大匹配有兩種求法，第一種是最大流（我在此假設(shè)讀者已有網(wǎng)絡(luò)流的知識(shí)）；第二種就是我現(xiàn)在要講的匈牙利算法。這個(gè)算法說白了就是最大流的算法，但是它跟據(jù)二分圖匹配這個(gè)問題的特點(diǎn)，把最大流算法做了簡化，提高了效率。匈牙利算法其實(shí)很簡單，但是網(wǎng)上搜不到什么說得清楚的文章。所以我決定要寫一下。
最大流算法的核心問題就是找增廣路徑（augment path）。匈牙利算法也不例外，它的基本模式就是：

初始時(shí)最大匹配為空
while 找得到增廣路徑
    do 把增廣路徑加入到最大匹配中去
可見和最大流算法是一樣的。但是這里的增廣路徑就有它一定的特殊性，下面我來分析一下。
（注：匈牙利算法雖然根本上是最大流算法，但是它不需要建網(wǎng)絡(luò)模型，所以圖中不再需要源點(diǎn)和匯點(diǎn)，僅僅是一個(gè)二分圖。每條邊也不需要有方向。）


圖1 圖2
圖1是我給出的二分圖中的一個(gè)匹配：［1，5］和［2，6］。圖2就是在這個(gè)匹配的基礎(chǔ)上找到的一條增廣路徑：3->6->2->5->1->4。我們借由它來描述一下二分圖中的增廣路徑的性質(zhì)：

(1)有奇數(shù)條邊。
(2)起點(diǎn)在二分圖的左半邊，終點(diǎn)在右半邊。
(3)路徑上的點(diǎn)一定是一個(gè)在左半邊，一個(gè)在右半邊，交替出現(xiàn)。（其實(shí)二分圖的性質(zhì)就決定了這一點(diǎn)，因?yàn)槎謭D同一邊的點(diǎn)之間沒有邊相連，不要忘記哦。）
(4)整條路徑上沒有重復(fù)的點(diǎn)。
(5)起點(diǎn)和終點(diǎn)都是目前還沒有配對(duì)的點(diǎn)，而其它所有點(diǎn)都是已經(jīng)配好對(duì)的。（如圖1、圖2所示，［1，5］和［2，6］在圖1中是兩對(duì)已經(jīng)配好對(duì)的點(diǎn)；而起點(diǎn)3和終點(diǎn)4目前還沒有與其它點(diǎn)配對(duì)。）
(6)路徑上的所有第奇數(shù)條邊都不在原匹配中，所有第偶數(shù)條邊都出現(xiàn)在原匹配中。（如圖1、圖2所示，原有的匹配是［1，5］和［2，6］，這兩條配匹的邊在圖2給出的增廣路徑中分邊是第2和第4條邊。而增廣路徑的第1、3、5條邊都沒有出現(xiàn)在圖1給出的匹配中。）
(7)最后，也是最重要的一條，把增廣路徑上的所有第奇數(shù)條邊加入到原匹配中去，并把增廣路徑中的所有第偶數(shù)條邊從原匹配中刪除（這個(gè)操作稱為增廣路徑的取反），則新的匹配數(shù)就比原匹配數(shù)增加了1個(gè)。（如圖2所示，新的匹配就是所有藍(lán)色的邊，而所有紅色的邊則從原匹配中刪除。則新的匹配數(shù)為3。）

不難想通，在最初始時(shí)，還沒有任何匹配時(shí)，圖1中的兩條灰色的邊本身也是增廣路徑。因此在這張二分圖中尋找最大配匹的過程可能如下：

(1)找到增廣路徑1->5，把它取反，則匹配數(shù)增加到1。
(2)找到增廣路徑2->6，把它取反，則匹配數(shù)增加到2。
(3)找到增廣路徑3->6->2->5->1->4，把它取反，則匹配數(shù)增加到3。
(4)再也找不到增廣路徑，結(jié)束。

當(dāng)然，這只是一種可能的流程。也可能有別的找增廣路徑的順序，或者找到不同的增廣路徑，最終的匹配方案也可能不一樣。但是最大匹配數(shù)一定都是相同的。

對(duì)于增廣路徑還可以用一個(gè)遞歸的方法來描述。這個(gè)描述不一定最準(zhǔn)確，但是它揭示了尋找增廣路徑的一般方法：
“從點(diǎn)A出發(fā)的增廣路徑”一定首先連向一個(gè)在原匹配中沒有與點(diǎn)A配對(duì)的點(diǎn)B。如果點(diǎn)B在原匹配中沒有與任何點(diǎn)配對(duì)，則它就是這條增廣路徑的終點(diǎn)；反之，如果點(diǎn)B已與點(diǎn)C配對(duì)，那么這條增廣路徑就是從A到B，再從B到C，再加上“從點(diǎn)C出發(fā)的增廣路徑”。并且，這條從C出發(fā)的增廣路徑中不能與前半部分的增廣路徑有重復(fù)的點(diǎn)。

比如圖2中，我們要尋找一條從3出發(fā)的增廣路徑，要做以下3步：
(1)首先從3出發(fā)，它能連到的點(diǎn)只有6，而6在圖1中已經(jīng)與2配對(duì)，所以目前的增廣路徑就是3->6->2再加上從2出發(fā)的增廣路徑。
(2)從2出發(fā)，它能連到的不與前半部分路徑重復(fù)的點(diǎn)只有5，而且5確實(shí)在原匹配中沒有與2配對(duì)。所以從2連到5。但5在圖1中已經(jīng)與1配對(duì)，所以目前的增廣路徑為3->6->2->5->1再加上從1出發(fā)的增廣路徑。
(3)從1出發(fā)，能連到的不與自已配對(duì)并且不與前半部分路徑重復(fù)的點(diǎn)只有4。因?yàn)?在圖1中沒有與任何點(diǎn)配對(duì)，所以它就是終點(diǎn)。所以最終的增廣路徑是3->6->2->5->1->4。

但是嚴(yán)格地說，以上過程中從2出發(fā)的增廣路徑（2->5->1->4）和從1出發(fā)的增廣路徑（1->4）并不是真正的增廣路徑。因?yàn)樗鼈儾环锨懊嬷v過的增廣路徑的第5條性質(zhì)，它們的起點(diǎn)都是已經(jīng)配過對(duì)的點(diǎn)。我們?cè)谶@里稱它們?yōu)?#8220;增廣路徑”只是為了方便說明整個(gè)搜尋的過程。而這兩條路徑本身只能算是兩個(gè)不為外界所知的子過程的返回結(jié)果。
顯然，從上面的例子可以看出，搜尋增廣路徑的方法就是DFS，可以寫成一個(gè)遞歸函數(shù)。當(dāng)然，用BFS也完全可以實(shí)現(xiàn)。

至此，理論基礎(chǔ)部份講完了。但是要完成匈牙利算法，還需要一個(gè)重要的定理：

如果從一個(gè)點(diǎn)A出發(fā)，沒有找到增廣路徑，那么無論再從別的點(diǎn)出發(fā)找到多少增廣路徑來改變現(xiàn)在的匹配，從A出發(fā)都永遠(yuǎn)找不到增廣路徑。

要用文字來證明這個(gè)定理很繁，話很難說，要么我還得多畫一張圖，我在此就省了。其實(shí)你自己畫幾個(gè)圖，試圖舉兩個(gè)反例，這個(gè)定理不難想通的。（給個(gè)提示。如果你試圖舉個(gè)反例來說明在找到了別的增廣路徑并改變了現(xiàn)有的匹配后，從A出發(fā)就能找到增廣路徑。那么，在這種情況下，肯定在找到別的增廣路徑之前，就能從A出發(fā)找到增廣路徑。這就與假設(shè)矛盾了。）
有了這個(gè)定理，匈牙利算法就成形了。如下：
初始時(shí)最大匹配為空
for 二分圖左半邊的每個(gè)點(diǎn)i
    do 從點(diǎn)i出發(fā)尋找增廣路徑。如果找到，則把它取反（即增加了總了匹配數(shù)）。

如果二分圖的左半邊一共有n個(gè)點(diǎn)，那么最多找n條增廣路徑。如果圖中共有m條邊，那么每找一條增廣路徑（DFS或BFS）時(shí)最多把所有邊遍歷一遍，所花時(shí)間也就是m。所以總的時(shí)間大概就是O（n * m）。

posted on 2008-11-29 13:08 蝸牛 閱讀(1320) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM ICPC