先來講講什么是二分圖拘哨，一個圖的點如果可以被分成兩個集合米碰，并且任何一個邊的兩個端點都不在一個集合中补憾，那么這個圖就是二分圖
如圖
二分圖匹配的解決的又是什么問題叛拷？
現(xiàn)在有一些男生和一些女生在舞池聚會报亩，現(xiàn)在他們要跳舞浴鸿，每個人只愿意跟自己喜歡的異性跳舞，這個喜歡是相互的（即男喜歡此女弦追，此女必定也喜歡此男岳链，因為二分圖是無向圖），并且一個人只能跳一次舞劲件，現(xiàn)在告訴你他們互相的喜歡關(guān)系掸哑，問最多可以跳幾次舞蹈哈
前人的智慧總是無窮的，引用了一位洛谷大佬的題解來講一下匈牙利匹配零远，原題解
https://www.luogu.com.cn/problemnew/solution/P3386
匈牙利的本質(zhì)是協(xié)商或者說退讓苗分，讓我們來用圖看一下，下圖的連線表示喜歡關(guān)系
當兩個男生出現(xiàn)沖突（即兩個人選中同一個女生）牵辣，序號小的要考慮讓步去選序號大的女生摔癣，如果無法讓步（即沒有其他可選），則不退讓服猪。
可能有點抽象供填，不要緊，我們來看圖
每個人物代表一個點罢猪，連線代表可以處的cp（即可以進行的匹配）
開始匹配近她，毫無疑問男一匹配女一，沒有問題膳帕，已經(jīng)匹配的關(guān)系用藍色線表示
然后葉修來了粘捎，他也想要女一薇缅，這咋整，黃少看了一下攒磨，自己還可以選可愛的妹妹泳桦，他說那行，女一讓給你了娩缰，我要妹妹（女三）灸撰，于是圖變成了這樣
更麻煩的來了，張新杰也要女一拼坎，要跟葉修搶浮毯，葉修表示我還有初音，那女一就給你了泰鸡，然后圖是這樣的
本篇最慘男主登場债蓝，他也喜歡女一，他問男三能不能把女一讓給他啊盛龄，男三找了一下發(fā)現(xiàn)他沒有其他能選的饰迹，于是孫翔被拒絕了，本場單身狗誕生了余舶，匹配沒法進行下去了啊鸭，匈牙利算法結(jié)束！所以匹配數(shù)為3匿值！
觀察一下莉掂，本質(zhì)是讓步，只要出現(xiàn)沖突千扔，序號小的那個要考慮讓步，能讓就讓库正，如果不能讓步（即找不到其他妹子和自己配對）就拒絕讓步的要求曲楚，讓后面那個人不要和他搶，去找其他的女生褥符，如果后面這個人把自己喜歡的妹子都嘗試一遍都不行龙誊，那就單著吧
老規(guī)矩，結(jié)合題目看代碼喷楣，題目：https://www.luogu.com.cn/problem/P3386
這是個裸題趟大，我們直接建圖跑匈牙利算法（默認o1/就是成對輸入的第一個點那邊是左）
介紹兩個數(shù)組，parent數(shù)組铣焊，顧名思義逊朽，就是存右邊的點是跟誰匹配的，是已經(jīng)確定的匹配曲伊，par[3]=2代表左2和右3匹配叽讳，bool類型used數(shù)組則是代表嘗試匹配，或者說是被預(yù)定，used[2]=1代表右2被預(yù)定了岛蚤，在嘗試讓步的過程中不能嘗試2號點邑狸，hh這么說確實抽象，看代碼就明白了
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
struct xing
{
int qian,wei;
}bian[1000010];
int n,m,e,u,v,parent[1010],cnt,head[1010],ans,used[1010];
void add(int o1,int o2)
{
bian[++cnt].qian=head[o1];
bian[cnt].wei=o2;
head[o1]=cnt;
}
bool find(int u)
{
for(int i=head[u];i;i=bian[i].qian)
{//遍歷邊涤妒，就是挨個嘗試右邊的點能不能跟自己匹配
int v=bian[i].wei;
if(!used[v]){//如果沒有被預(yù)定
used[v]=1;//那我就要了单雾，即使這個v點在之前已經(jīng)有配偶了，即par[v]不為0她紫，那我也要了硅堆，本來和這個v點匹配的左邊的點嘗試讓步
if(parent[v]==0||find(parent[v]))//兩種情況，第一種情況：如果par[v]為0說明在之前還沒有人和v點確定匹配關(guān)系犁苏，那我就直接要了硬萍，第二種情況：如果已經(jīng)有人和v匹配了，那么就請par[v]去試試能不能換個人匹配围详，把v點讓給我朴乖，如果可以，那v這個點我也要了（是不是和之前的匹配圖對上了）
{
parent[v]=u;//確定匹配關(guān)系
return 1;//返回真值助赞，意思是這個傳入?yún)?shù)u點匹配上了
}
}
}
return 0;//如果遍歷所有的邊這個u點都沒匹配上买羞，不管是因為他根本沒有喜歡的人還是他喜歡的人都被占了同時還沒有讓步給他，反正他是單著了（無遞歸）或者返回給之前讓u點嘗試讓步的點一個不能讓步的信息（遞歸進去了）
}
int main()
{
int o1,o2;
cin>>n>>m>>e;//一邊有n個點雹食，另外一邊有m個點畜普，一共有e個關(guān)系
while(e--){//根據(jù)輸入的關(guān)系建邊
cin>>o1>>o2;
if(o1>n||o2>m)//如果輸入不合法，忽略他
continue;
add(o1,o2);//這里為了方便群叶，其實是用的單向邊吃挑，因為沒有必要雙向，之前說喜歡關(guān)系是相互的是方便理解街立，但是跑算法只需要單邊就行了舶衬，數(shù)據(jù)幫你劃分了兩個集合了
}
for(int i=1;i<n+1;i++){
memset(used,0,sizeof(used));//嘗試對新的左邊的點進行匹配，現(xiàn)在used數(shù)組要清0
if(find(i))//如果這個新點可以匹配赎离，匹配數(shù)就++
ans++;
}
cout<<ans;
return 0;
}
這個遞歸過程我寫的可能還是有點不太明白逛犹，hh，問題不大梁剔，這種算法寫一遍就能理解了虽画，光看肯定是不行的，下篇見
