[ bipartite graph multiple matching ] 二分圖多重匹配增廣路算法

這種問題的題目通常是這樣:

給一張圖G有n1個點和n2個點，n1個點之間沒有邊，n2個點之間也沒有邊，但是n1和n2個點之間有m條邊(簡單的來說就是n1個點和n2個點的二分圖啦)，沒有重邊；其中n2個點每個點$u$都有一個可接受匹配數 $c_u$。
n1的點只能跟一個點匹配，但n2的點在不超過可接受匹配數的情況下，可以跟多個點匹配，求這張圖的最大匹配

通常可以利用拆點的方法或是flow來做，但是這樣空間跟效率都不是很好，這裡提供一個有效率的方法:

	#define MAXN1 1005
	#define MAXN2 505
	int n1,n2;//n1個點連向n2個點，其中n2個點可以匹配很多邊
	vector<int > g[MAXN1];//圖
	int c[MAXN2];//每個屬於n2點最多可以接受幾條匹配邊
	vector<int> match_list[MAXN2];//每個屬於n2的點匹配了那些點
	bool vis[MAXN2];//是否走訪過
	bool dfs(int u){
	for(size_t i=0;i<g[u].size();++i){
	int v=g[u][i];
	if(vis[v])continue;
	vis[v]=true;
	if((int)match_list[v].size()<c[v]){
	match_list[v].push_back(u);
	return true;
	}else{
	for(size_t j=0;j<match_list[v].size();++j){
	int next_u=match_list[v][j];
	if(dfs(next_u)){
	match_list[v][j]=u;
	return true;
	}
	}
	}
	}
	return false;
	}
	inline int max_match(){
	for(int i=0;i<n2;++i)match_list[i].clear();
	int cnt=0;
	for(int u=0;u<n1;++u){
	memset(vis,0,sizeof(bool)*n2);
	if(dfs(u))++cnt;
	}
	return cnt;
	}

view raw Augmenting Path multiple.cpp hosted with ❤ by GitHub

複雜度分析:
設n2個點每個點$u$都有一個值$E_u$表示和$u$相鄰的邊數，則總複雜度為
$$\ord{n1*(\sum{c_u*E_u}+n1+n2)}$$