【二分圖】[LUOGU 3386] 二分圖最大比對

二分圖，，，，一個不得不接觸的東西了（主要是想學網絡流了，，聽大佬說要先從二分圖學起，，那就隻能先學二分圖了，，ヽ(ー_ー)ノ）

（這次就打算改一下學習記錄的風格，按類似的專題來寫，這樣，，部落格不會寫太長，導緻不好找，，，）

（表示在寫這篇部落格的時候，，，被大寶寶syk叫回去睡覺了，，，隻能第二天再補(〃＞＿＜;〃)）

（接着補，，，）

，，進入正題：

二分圖呢，是要吧一幅圖上的點分成兩個獨立的點集使得這各個個點集中的點互相不連邊，而且一副無向圖為二分圖的充要條件是圖中的所有回路的長度均為偶數。（如果是奇數的話就可以了解為展開之後形成是有環的）

然後就介紹下比對，比對（或稱獨立邊集）是指這個圖之中，任意兩條邊都沒有公共的頂點。這時每個頂點都至多連出一條邊，而每一條邊都将一對頂點相比對。

求最大比對的話就是找到一個最大的邊集，使得比對數最多。

那，怎麼解決這樣的問題呢？？？

這就引出了經典的算法——匈牙利算法

先介紹一下增廣路：就是這條路徑将兩個不同集合的兩個未比對頂點通過一系列比對頂點相連。

匈牙利算法：

1. 匈牙利算法尋找最大比對，就是通過不斷尋找原有比對的增廣路徑，因為找到一條比對的增廣路徑，就意味着一個更大的比對 , 其恰好比多一條邊。
2. 對于圖來說，最大比對不是唯一的，但是最大比對的大小是唯一的。

題目：

幾道最大比對的闆子題。

LUOGU 3386

HDU 2063

HDU 1083/POJ 1469

代碼：

（這裡隻貼上LUOGU 3386的AC代碼，其他的題幾乎都一樣，都是闆子題）

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int sea=1010;
int n,m,k,ans;
int a[sea][sea],pre[sea],v[sea];
bool hgry(int x)
{
	for(int i=1;i<=m;i++)
	if(!v[i]&&a[x][i])
	{
		v[i]=1;
		if(!pre[i]||hgry(pre[i]))
		{pre[i]=x; return 1;}
	}
	return 0;
}
int main()
{
	n=read(); m=read(); k=read();
	memset(pre,0,sizeof(pre));
	for(int i=1;i<=k;i++) 
	{
		int x=read(),y=read(); 
		a[x][y]=1;
	}
	for(int i=1;i<=n;i++)
	{
		memset(v,0,sizeof(v));
		if(hgry(i)) ans++;
	}
	printf("%d\n",ans);
	return 0;
}
           

Continue……