1、二分圖、最大匹配
什麼是二分圖：二分圖又稱作二部圖，是圖論中的一種特殊模型。 設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，並且圖中的每條邊i，j）所關聯的兩個頂點i和j分別屬於這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖。 
什麼是匹配：把上圖想象成3男4女搞對象無同性戀），連線代表彼此有好感，但最終只能1夫1妻，最終的配對結果連線就是一個匹配。匹配可以是空。
什麼是最大匹配：在有好感的基礎上，能夠最多發展幾對。
現在要用匈牙利算法找出最多能發展幾對。
[color=green][size=medium]
匈牙利算法是解決尋找二分圖最大匹配的。
二、最大匹配與最小點覆蓋
最小點覆蓋：假如選了一個點就相當於覆蓋了以它為端點的所有邊，你需要選擇最少的點來覆蓋所有的邊
最小割定理是一個二分圖中很重要的定理：一個二分圖中的最大匹配數等於這個圖中的最小點覆蓋數。
最小點集覆蓋==最大匹配。在這裡解釋一下原因，首先，最小點集覆蓋一定>=最大匹配，因為假設最大匹配為n，那麼我們就得到了n條互不相鄰的邊，光覆蓋這些邊就要用到n個點。現在我們來思考為什麼最小點擊覆蓋一定<=最大匹配。任何一種n個點的最小點擊覆蓋，一定可以轉化成一個n的最大匹配。因為最小點集覆蓋中的每個點都能找到至少一條只有一個端點在點集中的邊如果找不到則說明該點所有的邊的另外一個端點都被覆蓋，所以該點則沒必要被覆蓋，和它在最小點集覆蓋中相矛盾），只要每個端點都選擇一個這樣的邊，就必然能轉化為一個匹配數與點集覆蓋的點數相等的匹配方案。所以最大匹配至少為最小點集覆蓋數，即最小點擊覆蓋一定<=最大匹配。綜上，二者相等。
三、匈牙利算法
先給一個例子
1、起始沒有匹配 
2、選中第一個x點找第一跟連線 
3、選中第二個點找第二跟連線 
4、發現x3的第一條邊x3y1已經被人占了，找出x3出發的的交錯路徑x3-y1-x1-y4，把交錯路中已在匹配上的邊x1y1從匹配中去掉，剩余的邊x3y1 x1y4加到匹配中去 
5、同理加入x4,x5。
匈牙利算法可以深度有限或者廣度優先，剛才的示例是深度優先，即x3找y1,y1已經有匹配，則找交錯路。若是廣度優先，應為：x3找y1,y1有匹配，x3找y2。
深度優先匈牙利算法代碼：
#define maxn 10//表示x集合和y集合中頂點的最大個數！
int nx,ny;//x集合和y集合中頂點的個數
int edge[maxn][maxn];//edge[i][j]為1表示ij可以匹配
int cx[maxn],cy[maxn];//用來記錄x集合中匹配的y元素是哪個！
int visited[maxn];//用來記錄該頂點是否被訪問過！
int path(int u)
{
int v;
for(v=0;v<ny;v++)
{
if(edge[u][v]&&!visited[v])
{
visited[v]=1;
if(cy[v]==-1||path(cy[v]))//如果y集合中的v元素沒有匹配或者是v已經匹配，但是從cy[v]中能夠找到一條增廣路
{
cx[u]=v;
cy[v]=u;
return 1;
}
}
}
return 0;
}
int maxmatch()
{
int res=0;
memset(cx,0xff,sizeof(cx));//初始值為-1表示兩個集合中都沒有匹配的元素！
memset(cy,0xff,sizeof(cy));
for(int i=0;i<=nx;i++)
{
if(cx[i]==-1)
{
memset(visited,0,sizeof(visitited));
res+=path(i);
}
}
return res;
}四、相關POJ題目
(1) poj3041
題目意思就是一顆子彈可以干掉任意一行或一列的障礙，問最少需要花費多少子彈清除呢
也就是求最小點集覆蓋。
#include<iostream>
#include<stdio.h>
#include<string.h>
#define Max 505
using namespace std;
int a[Max][Max];
int visit[Max];
int match[Max];
int N,K;
int path(int u)
{
int v;
for(v=1;v<=N;v++)
{
if(a[u][v] && !visit[v])
{
visit[v] = 1;
if(match[v] == -1 || path(match[v]))
{
match[v] = u;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,k,count;
scanf("%d %d",&N,&K);
memset(a,0,sizeof(a));
memset(match,-1,sizeof(match));
count = 0;
for(i=1;i<=K;i++)
{
scanf("%d %d",&j,&k);
a[j][k] = 1;
}
for(i=1;i<=N;i++)
{
memset(visit,0,sizeof(visit));
if(path(i))
count++;
}
printf("%d\n",count);
return 0;
}(2) poj3020
此題重要的是做出圖來，以什麼樣的觀點作圖。可以畫 h*w -> h*w 的圖，點i與上下左右四個點有邊存在，求最大匹配，最後結果為 總點數 - 最大匹配/2
#include<iostream>
#include<stdio.h>
#include<string.h>
#define Max 520
using namespace std;
int a[Max][Max];
int visit[Max];
int match[Max];
int N;
char str[50][15];
int path(int u)
{
int v;
for(v=1;v<=N;v++)
{
if(a[u][v] && !visit[v])
{
visit[v] = 1;
if(match[v] == -1 || path(match[v]))
{
match[v] = u;
return 1;
}
}
}
return 0;
}
int Find()
{
int count = 0;
int i;
for(i=1;i<=N;i++)
{
memset(visit,0,sizeof(visit));
if(path(i))
count++;
}
return count;
}
int init(int h,int w) {
int ctr,i,j;
int x,y;
int s,d;
ctr=0;
for ( i=1;i<=h;i++ ) {
for ( j=1;j<=w;j++ ) {
if ( str[i][j]=='*' ) {
ctr++;
x=i;
y=j;
s=(x-1)*w+y;
if ( y+1<=w&&str[x][y+1]=='*' ) {
d=(x-1)*w+y+1;
a[s][d]=1;
}
if ( x+1<=h&&str[x+1][y]=='*' ) {
d=(x)*w+y;
a[s][d]=1;
}
if ( y-1>=1&&str[x][y-1]=='*' ) {
d=(x-1)*w+y-1;
a[s][d]=1;
}
if ( x-1>=1&&str[x-1][y]=='*' ) {
d=(x-2)*w+y;
a[s][d]=1;
}
}
}
}
return ctr;
}
int main()
{
int i,j,k,n,totalnum,matchnum,h,w;
scanf("%d",&n);
while(n--)
{
memset(a,0,sizeof(a));
memset(match,-1,sizeof(match));
scanf("%d %d",&h,&w);
getchar();
for(i=1;i<=h;i++)
{
for(j=1;j<=w;j++)
{
scanf("%c",&str[i][j]);
}
getchar();
}
totalnum = init(h,w);
N = h*w;
matchnum = Find();
printf("%d\n",totalnum - matchnum/2);
}
return 0;
}二分圖
