二分图
定义
二分图，又叫二部图，即为节点由两个集合构成，且两个集合内部没有边的图。
换而言之，对于二分图而言，存在着一种划分方案使得节点构成满足上述性质的两个集合。
性质
二分图中的任意一条边分别连接两个集合中的一个点。
推论：二分图中不存在着长度为奇数的环。
判定
如何判定一张图为二分图：dfs或者bfs对图进行遍历，如果存在奇环，那么就不是二分图，反之是。
应用
二分图匹配
匹配
设G为二分图，若在G的子图M中，任意两条边都没有公共节点，那么称M为二分图G的一个匹配，且M的边数为匹配数。
完备匹配
设为二分图，，M为G中一个最大匹配，且，则称M为到的完备匹配。
完美匹配
一个二分图中两个点集的点数量相等，存在一个匹配包含两个点集中所有的点，则该匹配为完美匹配。
最优匹配
二分图中权值之和最大的完备匹配称为最优匹配。
最大匹配
最大匹配就是一个图所有的匹配中，所含匹配边数量最多的匹配，叫做最大匹配。
寻找二分图边数最大的匹配叫做最大匹配问题，无权二分图的最大匹配问题可以使用匈牙利算法进行解决，时间复杂度为O(VE)。
交替路：从一个未匹配点出发，依次经过匹配边，非匹配边，匹配边…形成的路径叫做交替路
增广路：从一个未匹配点出发，走交替路，最终到达另一个未匹配点，则这条路径叫做增广路。
增广路有一个非常重要的特点，非匹配边的数量较匹配边多1，因此只要将增广路中匹配边和非匹配边交换，那么图中的匹配边数量就增加1。匈牙利算法的本质就是不断寻找增广路，将匹配数不断加1，直到找不到增广路，就实现了一个最大匹配。
所有的匹配算法都基于增广路定理：一个匹配是最大匹配当且仅当没有增广路，该定理适用于所有图。
匈牙利算法的大致流程：
1.首先从任意一个未匹配点u开始，选择它的任意一条边（u-v），如果此时v没有配对，则匹配成功，匹配数加一，若v已经配对，则尝试寻找v的配对的另一个配对（该步骤递归执行）,若该尝试成功，则配对成功，配对数加一。
2.若上一步配对不成功，那么重新选择一条未被选择过的边，重复上一步。
3.对剩下每一个没有配对的点执行步骤1，直到所有的点都被尝试完毕。
洛谷P3386 【模板】二分图匹配
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
int nx,ny,k;
int edge[maxn][maxn];
int cx[maxn],cy[maxn];
int vis[maxn];
int path(int u){
int v;
for(v = 1; v <= ny; v++){
if(edge[u][v] && !vis[v]){
vis[v] = 1;
if(cy[v]==-1||path(cy[v])){
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
int maxMatch(){
int res = 0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
for(int i = 1; i <= nx; i++){
// if(cx[i] == -1){
memset(vis,0,sizeof(vis));
res+=path(i);
// }
}
return res;
}
int main(){
cin>>nx>>ny>>k;
int a,b;
for(int i = 1; i <= k; i++){
cin>>a>>b;
if(a <= nx && b <= ny) edge[a][b] = 1;
}
cout<<maxMatch()<<"\n";
return 0;
}
洛谷CF862B Mahmoud and Ehab and the bipartiteness
给出n个点,n-1条边，求增加多少条边能够使该图成为一张二分图。
利用二分图的判定，dfs染色，答案为num[黑]*num[白]-(n-1)
题意是给定n和s，n代表n个人，每个人有一个id，其值为s+1,s+2,,,,s+n，对这n个人进行排序，保证每个人的位置能整除id。
不难想到利用二分图匹配，问题在于n和s都很大，最大是1e9的。怎么优化呢，我们利用数论里面的一个结论，在1e9的范围内，任意两个相邻的素数小于等于282.所以对于n大于300的，都可以直接输出no。还有一个特殊情况，当n>s的时候，这时候构建出的两个点集是有大量重复的，这时候如果对n和s交换位置，之后n小于300，那么这种情况也是可以的。剩下的就是构建二分图求解。
Hopcroft-Karp算法
在匈牙利算法中,我们每次寻找一条增广路来增加匹配集合M.可以证明,每次找增广路的复杂度是O(E),一共需要增广O(V)次,因此总时间复杂度为O(VE)。为了降低时间复杂度,在Hopcroft-Karp算法中,我们在增加匹配集合M时,每次BFS寻找多条增广路（不相交）.可以证明,这样迭代次数最多为2V^0.5,所以,时间复杂度就降到了O(V^0.5E)。
Hopcroft-Karp算法原理 Hopcroft-Karp算法先使用BFS查找多条增广路，然后使用DFS遍历增广路（累加匹配数，修改匹配点集），循环执行，直到没有增广路为止。本质上就是对朴素匈牙利算法外面套了一层宽搜，减少了朴素匈牙利算法中查找增广路的次数。 Hopcroft-Karp算法的BFS遍历只对点进行分层（不对匹配点和未匹配点进行标记），然后用DFS遍历看上面的层次哪些是增广路径（最后一个点是未匹配的）。
算法步骤：
设U和V是图G的二分图，M是从U到V的匹配 (1)使用BFS遍历对图的点进行分层，从X中找出一个未匹配点v,（所有v)组成第一层，接下的层是这样形成的——都是查找匹配点（增广路性质），直到在V中找到未匹配点才终止查找，对X其他未匹配点同样进行查找增广路径（BFS只分层不标记是否匹配点） (2)使用DFS遍历查找(1)形成的增广路，找到就匹配数就累加1 (3)重复(1)(2)操作直到找不出增广路径为止
复杂度分析：
具体的分析这个复杂度实在是理解不能，严谨的复杂度证明在这：Hopcroft-Karp算法分析
大致概括一下，每一次BFS都会找出多条最小增广路然后DFS沿着搜出来的增广路进行匹配，这样一次BFS+DFS的复杂度是,然后很玄学的BFS的迭代次数被证明最多迭代次，所以时间复杂度最差应该是。
事实证明不懂复杂度并不影响我们使用HK算法，因为相较于实现很简单的匈牙利算法，HK算法的实现也很好写。
HDU1083
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 1e3+5;
const int INF = 0x3f3f3f3f;
int t,p,n;
vector<int> gra[maxn];
int dx[maxn],dy[maxn],cx[maxn],cy[maxn],vis[maxn];
//dx为左边点集的层数，dy为右边点集的层数
//cx为左边点集对应右边的另一个匹配点，cy为右边点集对应左边的另一个匹配点
int dis;
int bfs(){
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
queue<int> q;
dis = INF;
for(int i = 1; i <= p; i++){//找到所有未匹配点，压入队列
if(cx[i] == -1) {
dx[i] = 0;
q.push(i);
}
}
while(!q.empty()){
int u = q.front(); q.pop();
if(dx[u] > dis) break;//当前路径大于搜索的层数（层数即增广路径的长度）
int len = gra[u].size();
for(int i = 0 ; i < len; i++){
int v = gra[u][i];
if(dy[v] == -1){
dy[v] = dx[u] + 1;
if(cy[v] == -1) dis = dy[v];//找到未匹配点
else {
dx[cy[v]] = dy[v] +1;//若v已经匹配，则将v对应的匹配点压入队列并修改层数
q.push(cy[v]);
}
}
}
}
return dis != INF;
}
int dfs(int u){
int len = gra[u].size();
for(int i = 0; i < len; i++){
int v = gra[u][i];
if(dy[v] == dx[u] + 1 && !vis[v]) {//如果该点没有被遍历过并且为u的下一层
vis[v] = 1;
if(cy[v] != -1 && dy[v] == dis) continue;//v已经匹配且位于增广路径的最后，则必然不存在新的增广路径
if(cy[v] == -1 || dfs(cy[v])){
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
void HK(){
int ans = 0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while(bfs()){
memset(vis,0,sizeof(vis));
for(int i = 1; i <= p; i++){
if(cx[i] == -1 && dfs(i)) ++ans;
}
}
if(ans == p) printf("YES\n");
else printf("NO\n");
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&p,&n);
for(int i = 0; i <= p; i++) gra[i].clear();
for(int i = 1; i <= p; i++){
int k,a;
scanf("%d",&k);
for(int j = 1; j <= k; j++){
scanf("%d",&a); //事实证明cin比scanf慢了不止一点点
gra[i].push_back(a);
}
}
HK();
}
return 0;
}
二分图带权最优匹配
使用Kuhn-Munkers算法可以实现二分图的最优匹配，时间复杂度可以达到。
KM算法通过对每个点添加一个顶标，将求最大权匹配转化为求完备匹配的问题。设两个点集为X和Y，对于每一条边权值为，左边点的顶标为，右边点的顶标为，初始化为所有与该点连接的边的最大值，为0。在该算法中，始终保证。其中，所有构成的子图称为相等子图。
简单的讲KM算法流程分为以下几步：
1.初始化顶标值
2.使用匈牙利算法寻找完备匹配
3.未找到完备匹配则修改顶标值,扩大相等子图
4.重复2.3知道找到相等子图的完备匹配
具体的KM算法讲解看这里 KM算法
KM算法的应用：
1.求最大权匹配，如果不存在完备匹配，需要将不存在的权值赋值为0。
2.求最小全匹配，将所有的边权取反，求新图的最大权匹配，最后输出结果的相反数
3.求边权之积最大，对每条边取对数，求新图的最大权匹配，输出结果a的即可。
练习：
二分图的性质 以下内容摘自
预备知识：
点覆盖、最小点覆盖 点覆盖集即一个点集，使得所有边至少有一个端点在集合里。或者说是“点” 覆盖了所有“边”。。极小点覆盖(minimal vertex covering)：本身为点覆盖，其真子集都不是。最小点覆盖(minimum vertex covering)：点最少的点覆盖。点覆盖数(vertex covering number)：最小点覆盖的点数。
边覆盖、极小边覆盖 边覆盖集即一个边集，使得所有点都与集合里的边邻接。或者说是“边” 覆盖了所有“点”。极小边覆盖(minimal edge covering)：本身是边覆盖，其真子集都不是。最小边覆盖(minimum edge covering)：边最少的边覆盖。边覆盖数(edge covering number)：最小边覆盖的边数。
独立集、极大独立集 独立集即一个点集，集合中任两个结点不相邻，则称V为独立集。或者说是导出的子图是零图（没有边）的点集。极大独立集(maximal independent set)：本身为独立集，再加入任何点都不是。最大独立集(maximum independent set)：点最多的独立集。独立数(independent number)：最大独立集的点。
团 团即一个点集，集合中任两个结点相邻。或者说是导出的子图是完全图的点集。极大团(maximal clique)：本身为团，再加入任何点都不是。最大团(maximum clique)：点最多的团。团数(clique number)：最大团的点数。
边独立集、极大边独立集 边独立集即一个边集，满足边集中的任两边不邻接。极大边独立集(maximal edge independent set)：本身为边独立集，再加入任何边都不是。最大边独立集(maximum edge independent set)：边最多的边独立集。边独立数(edge independent number)：最大边独立集的边数。
边独立集又称匹配(matching)，相应的有极大匹配(maximal matching)，最大匹配(maximum matching)，匹配数(matching number)。
支配集、极小支配集 支配集即一个点集，使得所有其他点至少有一个相邻点在集合里。或者说是一部分的“点”支配了所有“点”。极小支配集(minimal dominating set)：本身为支配集，其真子集都不是。最小支配集(minimum dominating set)：点最少的支配集。支配数(dominating number)：最小支配集的点数。
边支配集、极小边支配集 边支配集即一个边集，使得所有边至少有一条邻接边在集合里。或者说是一部分的“边”支配了所有“边”。极小边支配集(minimal edge dominating set)：本身是边支配集，其真子集都不是。最小边支配集(minimum edge dominating set)：边最少的边支配集。边支配数(edge dominating number)：最小边支配集的边数。
最小路径覆盖 最小路径覆盖(path covering)：是“路径” 覆盖“点”，即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点，即每个顶点严格属于一条路径。路径的长度可能为0(单个点)。 最小路径覆盖数＝G的点数－最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。拆点：将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息，从X部往Y部引边。所有边的方向都是由X部到Y部。因此，所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数＝原图G的顶点数－二分图的最大匹配数便可以得解。
二分图的性质
二分图中，点覆盖数是匹配数。
(1) 二分图的最大匹配数等于最小覆盖数，即求最少的点使得每条边都至少和其中的一个点相关联，很显然直接取最大匹配的一段节点即可。
(2) 二分图的独立数等于顶点数减去最大匹配数，很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。
(3) DAG的最小路径覆盖，将每个点拆点后作最大匹配，结果为n-m，求具体路径的时候顺着匹配边走就可以，匹配边i→j’,j→k’,k→l’….构成一条有向路径。
（4）最大匹配数=左边匹配点+右边未匹配点。因为在最大匹配集中的任意一条边，如果他的左边没标记，右边被标记了，那么我们就可找到一条新的增广路，所以每一条边都至少被一个点覆盖。
（5）最小边覆盖=图中点的个数-最大匹配数=最大独立集。
Views: 98