傳送門

聲明幾個定義：

1.二分圖

對于一個圖G=（V,E），若能將其點集分為兩個互不相交的兩個子集X、Y，使得X∩Y=?，且對于G的邊集V，若其所有邊的頂點全部一側(cè)屬于X，一側(cè)屬于Y，則稱圖G為一個二分圖。?

2.二分圖匹配

對于一個二分圖G的子圖M,若M的邊集E的的任意兩條邊都不連接同一個頂點，則稱M為G的一個匹配。

3.最大匹配

對于二分圖G的一個子圖M，若M為其邊數(shù)最多的子圖，則稱M為G的最大匹配。

?

應用“匈牙利算法”求二分圖最大匹配。

這種算法可以這樣解釋：

建立有向圖G，分為二分圖的左側(cè)和右側(cè)。
優(yōu)先選擇左側(cè)序號更小的連接可能的邊。
若兩個點的目標點重復，則遞歸搜索任意一個點能否更換目標點，若不能則這種匹配無法成立。

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int mp[1010][1010],fri[1010],flg[1010]; int n,m,e,ans=0; int find(int x){for(int y=1;y<=m;y++){if(mp[x][y]&&!flg[y]){flg[y]=1;if(find(fri[y])||!fri[y]){fri[y]=x;return 1;} }}return 0; }int main() {cin>>n>>m>>e;for(int i=1;i<=e;i++){int u,v;cin>>u>>v;mp[u][v]=1;}for(int i=1;i<=n;i++){memset(flg,0,sizeof(flg));if(find(i)==1) ans++;}cout<<ans;return 0;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/charlesss/p/10297560.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。