一、關於匈牙利演算法

匈牙利演算法是由匈牙利數學家Edmonds提出的，用增廣路徑求二分圖最大匹配的演算法。

聽起來高端，其實說白了就是：

假設不存在單相思（單身狗偷偷抹眼淚），在一個同性戀不合法的國家裡（不存在任何歧視#正色），有一些男人和女人，他們互相之間存在一些互相愛戀的關係。而匈牙利演算法就是要促成儘量多的男女配對。

如下圖：

綠色標註的就是這張圖的一個最大二分圖匹配。

先提一個下麵會提到的名詞：
增廣路：若P是圖G中一條連通兩個未匹配頂點的路徑，並且屬於M的邊和不屬於M的邊（即已匹配和待匹配的邊)在P上交替出現，則稱P為相對於M的一條增廣路徑。

下麵講講匈牙利演算法的思路：
1、依次從一個部分的每個頂點出發，尋找一條增廣路；

2、遍歷所有以當前點為起點的邊，若找到一條增廣路，就更新匹配數，並返回1；否則重覆二，直至所有邊被遍歷；

3、若以當前點為起點的所有邊被遍歷仍未找到一條可增廣路，返回1。

顯然，由於尋找增廣路的過程需要深搜，所以匈牙利演算法是一個基於dfs的演算法。思路很簡單，所以我就不貼偽代碼了才不是因為懶而且還不會寫偽代碼（劃掉），反正hero是裸題，題解里也有模板。

二、HNOI2006 hero超級英雄題解

題目描述：

現在電視臺有一種節目叫做超級英雄,大概的流程就是每位選手到臺上回答主持人的幾個問題,然後根據回答問題的多少獲得不同數目的獎品或獎金。主持人問題準備了若幹道題目，只有當選手正確回答一道題後，才能進入下一題，否則就被淘汰。為了增加節目的趣味性並適當降低難度，主持人總提供給選手幾個“錦囊妙計”，比如求助現場觀眾，或者去掉若幹個錯誤答案（選擇題）等等。 這裡，我們把規則稍微改變一下。假設主持人總共有m道題，選手有n種不同的“錦囊妙計”。主持人規定，每道題都可以從兩種“錦囊妙計”中選擇一種，而每種“錦囊妙計”只能用一次。我們又假設一道題使用了它允許的錦囊妙計後，就一定能正確回答，順利進入下一題。現在我來到了節目現場，可是我實在是太笨了，以至於一道題也不會做，每道題只好藉助使用“錦囊妙計”來通過。如果我事先就知道了每道題能夠使用哪兩種“錦囊妙計”，那麼你能告訴我怎樣選擇才能通過最多的題數嗎？

輸入：

輸入文件的一行是兩個正整數n和m(0 < n <1001,0 < m < 1001)表示總共有n中“錦囊妙計”，編號為0~n-1，總共有m個問題。
以下的m行，每行兩個數，分別表示第m個問題可以使用的“錦囊妙計”的編號。
註意，每種編號的“錦囊妙計”只能使用一次，同一個問題的兩個“錦囊妙計”可能一樣。

輸出：

第一行為最多能通過的題數p。

樣例輸入：

5 6
3 2
2 0
0 3
0 4
3 2
3 2

樣例輸出：

4

數據範圍：

0 < n , m < 1001

絕對的裸題，裸得讓我懷疑這是我在bzoj上見到的。附上鏈接→_→http://www.lydsy.com/JudgeOnline/problem.php?id=1191

代碼如下：

 1 #include<stdio.h>
 2 #include<string.h>
 3 struct node
 4 {
 5     int v;
 6     int next;
 7 };
 8 node e[3010];
 9 int st[3010],cnt;
10 int n,m; 
11 bool vis[3010];//判斷當遍搜索中某條路徑是否被走過 
12 int link[3010];//判斷左右端點是否相連   link[i]=j代表錦囊i與問題j相連，特別的，當link[i]=0時表示i是一個未蓋點 
13 void build(int a,int b)
14 {
15     e[++cnt].v=b;
16     e[cnt].next=st[a];
17     st[a]=cnt;
18 }//建圖，問題連向錦囊 
19 bool dfs(int x)
20 {
21     int i;
22     for(i=st[x];i!=0;i=e[i].next)//依次枚舉當前以左端點為起點的邊 
23     {
24         if(vis[i])continue;//如果被枚舉邊已經被訪問過，就跳過這條邊 
25         vis[i]=true;
26         int temp=e[i].v;
27         if(!link[temp]||dfs(link[temp]))//若temp是一個未蓋點或從temp對應的問題開始有可增廣路，就將temp對應的問題更改為x，並且認為存在從x開始的增廣路 
28         {
29             link[temp]=x;
30             return true;
31         }
32     }
33     return false;
34 }
35 int main()
36 {
37     scanf("%d%d",&n,&m);
38     int a,b,i,ans=0;
39     for(i=1;i<=m;i++)
40     {
41         scanf("%d%d",&a,&b);
42         build(i,a);
43         build(i,b);
44     }//建圖，問題連向錦囊 
45     for(i=1;i<=m;i++)
46     {
47         memset(vis,false,sizeof(vis)); 
48         if(dfs(i))ans++;
49         else      break;//這句一定要加！一定要加！一定要加！說三遍 ←__ ← 最開始沒加無限WA，後來意識到這是個闖關游戲，一關沒過游戲結束，就不往後做了 
50     }
51     printf("%d",ans);
52     return 0;
53 }