題目描述：

給定一個二分圖，其中左半部包含n1個點（編號1~n1），右半部包含n2個點（編號1~n2），二分圖共包含m條邊。

數據保證任意一條邊的兩個端點都不可能在同一部分中。

請你求出二分圖的最大匹配數。

二分圖的匹配：給定一個二分圖G，在G的一個子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。

二分圖的最大匹配：所有匹配中包含邊數最多的一組匹配被稱為二分圖的最大匹配，其邊數即為最大匹配數。

輸入格式

第一行包含三個整數 n1、 n2 和 m。

接下來m行，每行包含兩個整數u和v，表示左半部點集中的點u和右半部點集中的點v之間存在一條邊。

輸出格式

輸出一個整數，表示二分圖的最大匹配數。

數據范圍

1≤n1,n2≤500,1≤u≤n1,1≤v≤n2,1≤m≤105

輸入樣例：

2 2 4 1 1 1 2 2 1 2 2

輸出樣例：

2

分析：

二分圖的最大匹配問題，就是對于二分圖而言，將左邊點集和右邊點集配對，求配對的最大成功數目。用y總的話說就是，將二分圖左邊的點集看作男生，右邊點集看作女生，每個男生都喜歡至少一個女生，現在找能湊成情侶的最大對數。

比如上圖左邊點集對應編號為1到5的男生，右邊點集對應1到5的女生，左邊點集有指向右邊點集的邊表明有好感關系、二分圖的最大匹配可以用匈牙利算法求解，具體步驟就是：1號男生和1號女生配對后，5號男生也喜歡1號女生，為了發揚堅持不懈的精神，盡管5號男生還有其他喜歡的女生，也要先盡力的得到1號女生。恰好此前和1號女生配對的1號男生還有另一個喜歡的2號妹紙，于是經過5號男生的勸說，1號男生就把1號女生讓給了5號男生，自己跑去和2號女生配對了。

具體的流程是，需要遍歷每一個左邊節點，然后用st數組表示有沒有嘗試和右邊的某個節點匹配過，這是為了防止重復比對，比如A嘗試和B匹配，但是失敗了，然后繼續嘗試和C匹配，在這之前應該將st數組的B節點標記為已訪問。另一個數組是match數組，表明右邊結點有沒有被其它左邊節點匹配上了，在匹配過程中，如果待匹配的節點沒有和其它節點匹配過，就匹配它，否則嘗試讓之前匹配它的節點換個節點進行匹配。也就是說看上一個妹紙，先看她有木有對象，沒有就在一起，有了就去和她男友商量，讓他換個對象，把女友讓給自己；如果對方男友換了對象，這時就可以和該妹紙在一起了，要是對方男友不肯讓，就只好嘗試再去考慮其他喜歡的女生了。

#include <iostream> #include <cstring> using namespace std; const int maxn = 505,maxm = 100005; int h[maxn],e[maxm],ne[maxm],idx; int n1,n2,m,match[maxn]; bool st[maxn]; void add(int a,int b){e[idx] = b,ne[idx] = h[a],h[a] = idx++; } bool find(int u){for(int i = h[u];i != -1;i = ne[i]){int j = e[i];if(!st[j]){//防止重復匹配st[j] = true;if(!match[j] || find(match[j])){match[j] = u;return true;}}}return false; } int main(){scanf("%d%d%d",&n1,&n2,&m);memset(h,-1,sizeof h);int u,v,res = 0;while(m--){scanf("%d%d",&u,&v);add(u,v);}for(int i = 1;i <= n1;i++){memset(st,false,sizeof st);if(find(i)) res++;}printf("%d\n",res);return 0; }

?

總結

以上是生活随笔為你收集整理的AcWing 861 二分图的最大匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。