文章目录

二分图定义

###什么是二分图
设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

二分图判定

二分图判定

二分图算法

博客推荐 ：链接
二分图二•二分图最大匹配之匈牙利算法
相关定理

匈牙利算法求最大匹配

  1. 遍历左节点
  2. 寻找增广路
  3. 如果找到增广路，则匹配++
const int maxn = 1000+10;
vector<int> G[maxn];// vector 存边
int match[maxn];// 匹配的点
bool used[maxn];// 每次寻找增广路的时候都需要标记是否找过这个节点
int N,M;
bool dfs(int v){// dfs 寻找增广路
	used[v] = true;
	for(int i = 0;i < G[v].size(); ++i){
		int u = G[v][i],w = match[u];
		if(w < 0||!used[w]&&dfs(w)){
		/* 如果该点未标记，表示找到增广路，或者沿着匹配找，找到增广路 ，修改匹配的节点*/
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}
int main(void)
{
    scanf("%d %d",&N,&M);
    
    while(M--){
    	int u,v;
    	scanf("%d %d",&u,&v);
    	G[u].Pb(v);
    	G[v].Pb(u);
	}
	int ans = 0;
	memset(match,-1,sizeof(match));
	for(int i = 1;i <= N; ++i){// 遍历左集合，每次寻找增广路
		if(match[i] < 0){
			memset(used,0,sizeof(used));
			if(dfs(i)){
				ans++;
			}
		}
	}
   cout<<ans<<endl;
   return 0;
}
KM算法求最大权完美匹配

O(n^4) 代码

const int maxn = 500+10;
int W[maxn][maxn],n;
int Lx[maxn],Ly[maxn]; // 顶标
int Left[maxn]; // 右边的点匹配到左边的点是哪一个
bool S[maxn],T[maxn]; //标记已经加入匹配的点
bool match(int i){
    S[i] =  true;
    for(int j = 1;j <= n; ++j)
       if(Lx[i]+Ly[j] == W[i][j]&&!T[j]){
        T[j] = true;
        if(!Left[j]||match(Left[j])){// 寻找增广路 
            Left[j] = i;
            return true; 
        } 
       }
       return false;
} 
void update(){// 修改顶标 
    int a =1<<30; // 求最小的修改量
    for(int i = 1;i <= n; ++i)
      if(S[i])
      for(int j = 1;j <= n; ++j)
         if(!T[j])
           a = min(a,Lx[i]+Ly[j]-W[i][j]);
    for(int i = 1;i <= n; ++i){// 修改顶标 
        if(S[i]) Lx[i] -= a;
        if(T[i]) Ly[i] += a;
    } 

}
void KM() {
  for(int i = 1; i <= n; i++) {
    Left[i] = Lx[i] = Ly[i] = 0;
    for(int j = 1; j <= n; j++)
      Lx[i] = max(Lx[i], W[i][j]);
  }
  for(int i = 1; i <= n; i++) {
    for(;;) {
      for(int j = 1; j <= n; j++) S[j] = T[j] = false;
      if(match(i)) break; else update();
    }
  }
}
邻接表存图
const int maxn = 500+5;
struct KM{
	int n;
	vector<int> G[maxn];
	int W[maxn][maxn];
	int Lx[maxn];
	int Ly[maxn];
	int Left[maxn];
	bool S[maxn],T[maxn];
	void init(int n){
		this->n = n;
		for(int i = 1;i <= n; ++i) G[i].clear();
		memset(W,0,sizeof(W));
	}
	void AddEdge(int u,int v,int w){
		G[u].push_back(v);
		W[u][v] = w;
	}
	bool match(int u){
		S[u] = true;
		for(int i =0;i < G[u].size(); ++i){
			int v = G[u][i];
			if(Lx[u]+Ly[v] == W[u][v]&&!T[v]){
				T[v] = true;
				if(Left[v] == -1||match(Left[v])){
				   Left[v] = u;
				   return true;	
				}
			}
		}
		return false;
	}
	void update(){
		int a = INF;
		for(int u = 0;u < n; ++u) 
		 if(S[u])
		   for(int i = 0;i < G[u].size(); ++i){
		   	int v = G[u][i];
		   	if(!T[v])
		   	  a = min(a,Lx[u]+Ly[v]-W[u][v]);
		   }
		for(int i = 0;i < n; ++i){
			if(S[i]) Lx[i] -= a;
			if(T[i]) Ly[i] += a;
		}
	}
	void solve(){
		for(int i = 0;i < n; ++i){
			Lx[i] = *max_element(W[i],W[i]+n);
			Left[i] = -1;
			Ly[i] = 0;
		}
		for(int u = 0;u < n; ++u){
			for(;;){
				for(int i = 0;i < n; ++i) S[i] = T[i]  = 0;
				if(match(u)) break;
				else update();
			}
		}
	}
};

稳定婚姻问题

Ladies’ Choice
stable marriage problem
女士不停的求婚，然后男士选择，对女士来说选择最优

二分图相关定理

①最小路径覆盖：


#####②最小点覆盖
二分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖），叫做最小点覆盖。
最小点覆盖数 = 最大匹配数
证明（摘自http://www.matrix67.com/blog/archives/116）

③最大独立集=总数-最小覆盖集证明：

（摘自：http://m.blog.csdn.NET/article/details?id=50011363）

例题

  1. Ants POJ - 3565
    tree和ant的二分匹配问题，求最小权，转化成负数，就是求最大权
  2. Golden Tiger Claw UVA - 11383
    利用KM算法中相等子图的性质来做
  3. room
    把每个房间当成一个节点，匹配值是相同的人数，求最大权匹配，求出不用动的最大人数，取反就是需要改变房间的人数
  4. Girls and Boys HDU - 1068
    最大独立集 = 顶点数-最大匹配
    参考代码
  5. 整数规划 HDU - 6346 & 奔小康赚大钱 HDU - 2255