二分图总结
定义
二分图是指对于一个图G=（V,E），若能将其点集分为两个互不相交的两个子集X、Y，
使得X∩Y=∅，且对于G的边集V，若其所有边的顶点全部一侧属于X，
一侧属于Y，则称图G为一个二分图。
清晰明了
匹配
对于一个二分图G的子图M,若M的边集E的的任意两条边都不连接同一个顶点，
则称M为G的一个匹配。
最大匹配就是最大化M
方法
1.匈牙利算法
时间复杂度\(O(nm)\)
先前面的和前面的匹配
如果后来的和前面发生冲突，先试着让后来的优先，然后递归匹配前面的，如果发现前面的没有匹配的了，就还原。
/*
@Date : 2019-07-20 09:35:35
@Author : Adscn ([email protected])
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
const int MAXN=1007;
const int MAXM=1e6+7;
struct edge{
int v,nxt;
}e[MAXM];
int head[MAXN],cnt;
inline void add(int u,int v)
{
e[++cnt]=(edge){v,head[u]};
head[u]=cnt;
}
int n,m;
int match[MAXN],dfn[MAXN];
inline bool dfs(int p,int tim)
{
for(int i=head[p],v=e[i].v;i;i=e[i].nxt,v=e[i].v)
{
if(dfn[v]==tim)continue;
dfn[v]=tim;//被这一轮匹配了
if(match[v]==0||dfs(match[v],tim))
{
match[v]=p;
return true;
}
}
return false;
}
int main(void)
{
n=gi,m=gi;
int e=gi;
for(int i=1;i<=e;++i)
{
int u=gi,v=gi;
if(u>n||v>m)continue;
add(u,v);
}
int ans=0;
for(int i=1;i<=n;++i)ans+=dfs(i,i);
pi(ans);
return 0;
}2.最大流dinic
我们建立源点s,汇点t
将s到左点集连流量1的边，
左点集与右点集连流量1的边，
右点集连流量1的边到t
最大流量就是最大匹配。
正确性显然
时间复杂度
\(跑得贼快O(\text{跑得贼快})\)
/*
@Date : 2019-07-20 10:15:01
@Author : Adscn ([email protected])
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
const int MAXN=1007*2;
const int MAXM=1e6+7+MAXN;
const int inf=2147483647;
struct edge{
int v,nxt,flow;
}e[MAXM<<1];
int head[MAXN],cnt;
int cur[MAXN];
inline void add(int u,int v,int f)
{
e[cnt]=(edge){v,head[u],f};
head[u]=cnt++;
}
inline void link(int u,int v,int f){add(u,v,f),add(v,u,0);}
int n,m;
int dep[MAXN];
int maxflow=0;
inline bool bfs(int s,int t)
{
static int Q[MAXN],l,r;
Q[l=r=0]=s;
memset(dep,-1,sizeof dep);
dep[s]=0;
while(l<=r)
{
int p=Q[l++];
for(int i=head[p];~i;i=e[i].nxt)
{
int v=e[i].v;
if(dep[v]==-1&&e[i].flow)
{
dep[v]=dep[p]+1;
Q[++r]=v;
}
}
}
return ~dep[t];
}
inline int dfs(int p,int t,int restflow)
{
if(p==t||restflow==0)return restflow;
int sumflow=0;
for(int &i=cur[p],flow;~i;i=e[i].nxt)
{
int v=e[i].v;
if(e[i].flow&&dep[v]==dep[p]+1&&(flow=dfs(v,t,min(restflow,e[i].flow))))
{
restflow-=flow,sumflow+=flow;
e[i].flow-=flow,e[i^1].flow+=flow;
if(restflow==0)break;
}
}
return sumflow;
}
inline void dinic(int s,int t)
{
while(bfs(s,t))
memcpy(cur,head,sizeof head),maxflow+=dfs(s,t,inf);
}
int main(void)
{
n=gi,m=gi;
memset(head,-1,sizeof head);
int e=gi;
for(int i=1;i<=e;++i)
{
int u=gi,v=gi;
if(u>n||v>m)continue;
link(u,v+n,1);
}
int s=0,t=n+m+1;
for(int i=1;i<=n;++i)link(s,i,1);
for(int i=1;i<=m;++i)link(i+n,t,1);
dinic(s,t);
pi(maxflow);
return 0;
}判定
模板题NOIP2010关押罪犯
定理:
一个无向图是二分图，当且仅当图中不存在奇环
要判定非常简单，利用性质染色就可以了。
对于所有连通块，将相邻顶点染成不同颜色，如果已经是同色的就一定不是二分图。
代码略。
时间复杂度\(O(n)\)
一些有用的性质
最小点覆盖：取最少的点覆盖所有的边。
最小边覆盖：取最少的边覆盖所有的点
1.二分图中最小点覆盖等于最大匹配
证明显然
2.二分图中最小边覆盖等于顶点数-最大匹配
考虑给没被最大匹配的边匹配的点弄个虚拟点匹配上
然后我们最小边覆盖等于现在所有的匹配边的个数。
这个等于最大匹配+没匹配的点。
顶点数=最大匹配*2+没匹配的点。
所以，最小边覆盖=顶点数-最大匹配。