|
|
二分圖最大匹配的匈牙利算法： 二分圖是這樣一個圖，它的頂點可以分類兩個集合X和Y，所有的邊關聯在兩個頂點中，恰好一個屬于集合Ｘ，另一個屬于集合Ｙ。 最大匹配： 圖中包含邊數最多的匹配稱為圖的最大匹配。 完美匹配： 如果所有點都在匹配邊上，稱這個最大匹配是完美匹配。 最小覆蓋： 最小覆蓋要求用最少的點（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點關聯。可以證明：最少的點（即覆蓋數）＝最大匹配數 最小路徑覆蓋： 用盡量少的不相交簡單路徑覆蓋有向無環圖Ｇ的所有結點。解決此類問題可以建立一個二分圖模型。把所有頂點i拆成兩個：Ｘ結點集中的i和Y結點集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設二分圖最大匹配為m,則結果就是n-m。
二分圖最大匹配的經典匈牙利算法是由Edmonds在1965年提出的，算法的核心就是根據一個初始匹配不停的找增廣路，直到沒有增廣路為止。 匈牙利算法的本質實際上和基于增廣路特性的最大流算法還是相似的，只需要注意兩點： （一）每個X節點都最多做一次增廣路的起點； （二）如果一個Y節點已經匹配了，那么增廣路到這兒的時候唯一的路徑是走到Y節點的匹配點（可以回憶最大流算法中的后向邊，這個時候后向邊是可以增流的）。 找增廣路的時候既可以采用dfs也可以采用bfs，兩者都可以保證O(nm)的復雜度，因為每找一條增廣路的復雜度是O(m)，而最多增廣n次，dfs在實際實現中更加簡短。
算法思想： 算 法的思路是不停的找增廣軌, 并增加匹配的個數,增廣軌顧名思義是指一條可以使匹配數變多的路徑,在匹配問題中,增廣軌的表現形式是一條"交錯軌",也就 是說這條由圖的邊組成的路徑, 它的第一條邊是目前還沒有參與匹配的,第二條邊參與了匹配,第三條邊沒有..最后一條邊沒有參與匹配,并且始點和終點還沒 有被選擇過.這樣交錯進行,顯然 他有奇數條邊.那么對于這樣一條路徑,我們可以將第一條邊改為已匹配,第二條邊改為未匹配...以此類推.也就是將所有 的邊進行"反色",容易發現這樣修 改以后,匹配仍然是合法的,但是匹配數增加了一對.另外,單獨的一條連接兩個未匹配點的邊顯然也是交錯軌.可以證明, 當不能再找到增廣軌時,就得到了一個 最大匹配.這也就是匈牙利算法的思路.、 C鄰接矩陣： #include<stdio.h>
#include<string.h>
#include<math.h>
int result[105];
int state[105];
int data[105][105];
int n1,n2,m,ans;
int init()
{
int i,x,y;
memset(result,0,sizeof(result));
memset(data,0,sizeof(data));
scanf("%d%d%d",&n1,&n2,&m);
for (i=0;i<m ;i++ )
{
scanf("%d%d",&x,&y);
data[x][y]=1;
}
return 0;
}
int find(int x)
{
int i;
for (i=1;i<=n2 ;i++ )
{
if (data[x][i]==1 && !state[i])
{
state[i]=1;
if (result[i]==0 || find(result[i]))
{
result[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int i;
init();
ans=0;
for (i=1;i<=n1 ;i++ )
{
memset(state,0,sizeof(state));
if (find(i))
ans++;
}
printf("%d\n",ans);
return 0;
}
POJ_1274:  
#include<stdio.h>
#include<string.h>
#include<math.h>
int n,m,ans;
int link[205][205];
int state[205];
int result[205];
int find(int x)
{
int i;
for (i=1;i<=m ;i++ )
{
if (link[x][i] && !state[i])
{
state[i]=1;
if (result[i]==0 || find(result[i]))
{
result[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,Si,st;
while (scanf("%d%d",&n,&m)==2)
{
memset(link,0,sizeof(link));
memset(result,0,sizeof(result));
for (i=1;i<=n ;i++ )
{
scanf("%d",&Si);
for (j=1;j<=Si ;j++ )
{
scanf("%d",&st);
link[i][st]=1;
}
}
ans=0;
for (i=1;i<=n ;i++ )
{
memset(state,0,sizeof(state));
if (find(i))
ans++;
}
printf("%d\n",ans);
}
return 0;
}
|