描述
上一回我們已經将所有有問題的相親情況表剔除了，那麼接下來要做的就是安排相親了。因為過年時間并不是很長，是以姑姑希望能夠盡可能在一天安排比較多的相親。由于一個人同一天隻能和一個人相親，是以要從目前的相親情況表裡選擇盡可能多的組合，且每個人不會出現兩次。不知道有沒有什麼好辦法，對于目前給定的相親情況表，能夠算出最多能同時安排多少組相親呢？
同樣的，我們先将給定的情況表轉換成圖G=(V,E)。在上一回中我們已經知道這個圖可以被染成黑白兩色。不妨将所有表示女性的節點記為點集A，表示男性的節點記為點集B。則有A∪B=V。由問題可知所有邊e的兩個端點分别屬于AB兩個集合。則可以表示成如下的圖：
同樣的，我們将所有的邊分為兩個集合。集合S和集合M，同樣有S∪M=E。邊集S表示在這一輪相親會中将要進行的相親，邊集M表示在不在這一次進行。對于任意邊(u,v) ∈ S，我們稱u和v為一組比對，它們之間互相比對。在圖G，我們将邊集S用實線表示，邊集M用虛線表示。得到下圖：
則原問題轉化為，最多能選擇多少條邊到集合S，使得S集合中任何兩條邊不相鄰(即有共同的頂點)。顯然的，|S|<=Min{|A|, |B|}。
那麼能不能找到一個算法，使得能夠很容易計算出盡可能多的邊能夠放入集合S？我們不妨來看一個例子：
對于已經比對的點我們先不考慮，我們從未比對的點來做。這裡我們選擇A集合中尚未比對的點(A3和A4)考慮：
對于A3點，我們可以發現A3與B4右邊相連，且都未比對。則直接将(A3,B4)邊加入集合S即可。
對于A4點，我們發現和A4相連的B3，B4點都已經比對了。但是再觀察可以發現，如果我們将A2和B2相連，則可以将B3點空出來。那麼就可以同時将(A2,B2)，(A4,B3)相連。将原來的一個比對變成了兩個比對。
讓我們來仔細看看這一步：我們将這次變換中相關聯的邊标記出來，如下圖所示紫色的3條邊(A2,B2),(A2,B3),(A4,B3)。
這三條邊構成了一條路徑，可以發現這條路徑有個非常特殊的性質。虛線和實線互相交錯，并且起點和終點都是尚未比對的點，且屬于兩個不同的集合。我們稱這樣的路徑為交錯路徑。
再進一步分析，對于任意一條交錯路徑，虛線的數量一定比實線的數量多1。我們将虛線和實線交換一下，就變成了下面的圖：
在原來1個比對的基礎上，我們得到了2個新的比對，S集合邊的數量也增加了1。并且原來在已經比對的點仍然是已經比對的狀态。
再回頭看看A3點比對時的情況：對于(A3,B4)這一條路徑，同樣滿足了交錯路徑的性質。
至此我們得到了一個找新比對的有效算法：
選取一個未比對的點，查找是否存在一條以它為起點的交錯路徑。若存在，将該交錯路徑的邊虛實交換。否則在目前的情況下，該點找不到可以比對的點。
又有對于已經比對的點，該算法并不會改變一個點的比對狀态。是以當我們對所有未比對的點都計算過後，仍然沒有交錯路徑，則不可能找到更多的比對。此時S集合中的邊數即為最大邊數，我們稱為最大比對數。
那麼我們再一次梳理整個算法：
1. 依次枚舉每一個點i；
2. 若點i尚未比對，則以此點為起點查詢一次交錯路徑。
最後即可得到最大比對數。
在這個基礎上仍然有兩個可以優化的地方：
1.對于點的枚舉：當我們枚舉了所有A中的點後，無需再枚舉B中的點，就已經得到了最大比對。
2.在查詢交錯路徑的過程中，有可能出現Ai與Bj直接相連，其中Bj為已經比對的點，且Bj之後找不到交錯路徑。之後又通過Ai查找到了一條交錯路徑{Ai,Bx,Ay,…,Az,Bj}延伸到Bj。由于之前已經計算過Bj沒有交錯路徑，若此時再計算一次就有了額外的備援。是以我們需要枚舉每個Ai時記錄B集合中的點是否已經查詢過，起點不同時需要清空記錄。
僞代碼
輸入
第1行：2個正整數，N,M(N表示點數 2≤N≤1,000，M表示邊數1≤M≤5,000)
第2..M+1行：每行兩個整數u,v，表示一條無向邊(u,v)
輸出
第1行：1個整數，表示最大比對數
樣例輸入
5 4
3 2
1 3
5 4
1 5 樣例輸出
2
模闆模闆
#include <bits/stdc++.h>
#define MAXN 1510
using namespace std;
vector<int>G[MAXN];
int pipei[MAXN];
bool used[MAXN];
int N,T,M;
void init()
{
for(int i=0;i<N;i++)G[i].clear();
memset(G,0,sizeof(G));
}
void getMap()
{
int u,v;
for(int i=0;i<M;i++)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
}
int find(int x)
{
for(int i = 0; i <G[x].size(); i++)
{
int y = G[x][i];
if(!used[y])
{
used[y] = true;
if(pipei[y] == -1 || find(pipei[y]))
{
pipei[y] = x;
pipei[x] = y;
return 1;
}
}
}
return 0;
}
void solve()
{
int ans = 0;
memset(pipei, -1, sizeof(pipei));
for(int i = 1; i <=N; i++)
{
if(pipei[i]==-1)
{
memset(used, false, sizeof(used));
ans += find(i);
}
}
printf("%d\n",ans);
}
int main()
{
while(~scanf("%d%d",&N,&M))
{
init();
getMap();
solve();
}
return 0;
}