二分图学习笔记
chinaxjh
2019-11-15 08:25:49
# Part 1
## 二分图简介
二分图又称作二部图，是图论中的一种特殊模型。 设$G=(V,E)$是一个无向图，如果顶点V可分割为两个互不相交的子集$(A,B)$，并且图中的每条边$(i,j)$所关联的两个顶点i和j分别属于这两个不同的顶点集$(i\quad in\quad A,j\quad in\quad B)$，则称图$G$为一个二分图。
# Part 2
## 模板
#### 二分图判定
**判定定理：**
```
一张无向图是二分图：
当且仅当图中不存在奇环（奇环是指长度为奇数的环）
```
**染色法进行二分图判定**
[题目](https://www.luogu.org/problem/P1525)
- 1.我们尝试用黑和白两种颜色标记图中的点，当一个节点被标记了，那么所有与它相连的点应全部标记为相反的颜色
- 2.如果在标记过程中出现冲突，那么算法结束，证明本图中存在奇环，即本图不为二分图；反之，如果算法正常结束，那么证明本图是二分图
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N],b[N],las[N],nxt[N],color[N];
int len,n,m,i,l,r,bo,mid;
queue<int> q;
struct node
{
int x,y,z;
}aa[N];
bool cmp(node aa,node bb)
{
return aa.z>bb.z;
}
void add(int x,int y,int z)
{
len++;
a[len]=y;
b[len]=z;
nxt[len]=las[x];
las[x]=len;
}
bool check(int x)
{
int i,j;
while (q.size()) q.pop();
memset(color,0,sizeof(color));
for (i=1;i<=n;i++)
if (!color[i])
{
q.push(i);
color[i]=1;
while (q.size())
{
int xx;
xx=q.front();
q.pop();
for (j=las[xx];j;j=nxt[j])
if (b[j]<=x)
{
if (!color[a[j]])
{
q.push(a[j]);
if (color[xx]==1) color[a[j]]=2;
else color[a[j]]=1;
}
if (color[a[j]]==color[xx]) return false;
}
}
}
return true;
}
int main()
{
cin>>n>>m;
for (i=1;i<=m;i++) scanf("%d%d%d",&aa[i].x,&aa[i].y,&aa[i].z);
sort(aa+1,aa+1+m,cmp);
for (i=1;i<=m;i++)
{
add(aa[i].x,aa[i].y,i);
add(aa[i].y,aa[i].x,i);
}
bo=0; l=1; r=m;
while (l<=r)
{
mid=(l+r)>>1;
if (check(mid))
{
l=mid+1;
bo=mid;
} else r=mid-1;
}
cout<<aa[bo+1].z<<endl;
}
```
#### 最大匹配模板
[题目](https://www.luogu.org/problem/P3386)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2000003;
const int M=3003;
int a[N],nxt[N],las[N],opt_x[M],opt_y[M];
int len,n,m,e,i,x,y,ans;
bool vis[M];
void add(int x,int y)
{
len++;
a[len]=y;
nxt[len]=las[x];
las[x]=len;
}
bool dfs(int x)
{
int i,k;
for (i=las[x];i;i=nxt[i])
{
k=a[i];
if (vis[k]) continue;
vis[k]=true;
if (opt_y[k]==-1||dfs(opt_y[k]))
{
opt_x[x]=k;
opt_y[k]=x;
return true;
}
}
return false;
}
void hungary()
{
int i;
for (i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
ans+=dfs(i);
}
}
int main()
{
memset(opt_y,-1,sizeof(opt_y));
cin>>n>>m>>e;
for (i=1;i<=e;i++)
{
scanf("%d%d",&x,&y);
if (x>n||y>m) continue;
add(x,y);
}
hungary();
cout<<ans<<endl;
}
```
# Part 3
## 例题
#### 座位安排
[题目](https://www.luogu.org/problem/P2071)
二分图乱搞，右侧的点可以匹配两次，多开一个数组维护就好了。
注意如果在第一次匹配成功就可以退出了，第二次尝试匹配的活会占用（或者说空出）一个位置无法用于匹配，导致答案变小
```cpp
#include<bits/stdc++.h>
using namespace std;
const int M=10003;
int a[M],nxt[M],las[M],opt_x[M],opt_y[M],opt_z[M];
int len,n,m,e,i,x,y,ans;
bool vis[M];
void add(int x,int y)
{
len++;
a[len]=y;
nxt[len]=las[x];
las[x]=len;
}
bool dfs(int x)
{
int i,k;
for (i=las[x];i;i=nxt[i])
{
k=a[i];
if (vis[k]) continue;
vis[k]=true;
if (opt_y[k]==-1||dfs(opt_y[k]))
{
opt_x[x]=k;
opt_y[k]=x;
return true;
}
if (dfs(opt_z[k])||opt_z[k]==-1)
{
opt_x[x]=k;
opt_z[k]=x;
return true;
}
}
return false;
}
void hungary()
{
int i;
for (i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
ans+=dfs(i);
}
}
int main()
{
memset(opt_y,-1,sizeof(opt_y));
memset(opt_z,-1,sizeof(opt_z));
cin>>n;
n*=2;
for (i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
add(i,x);
add(i,y);
}
hungary();
cout<<ans<<endl;
}
```
#### 飞行员配对方案问题
[题目](https://www.luogu.org/problem/P3182)
比模板多了一个输出方案，其实匈牙利自带方案的
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1000003;
const int M=3003;
int a[N],nxt[N],las[N],opt_x[M],opt_y[M];
int len,n,m,e,i,x,y,ans;
bool vis[M];
void add(int x,int y)
{
len++;
a[len]=y;
nxt[len]=las[x];
las[x]=len;
}
bool dfs(int x)
{
int i,k;
for (i=las[x];i;i=nxt[i])
{
k=a[i];
if (vis[k]) continue;
vis[k]=true;
if (opt_y[k]==-1||dfs(opt_y[k]))
{
opt_x[x]=k;
opt_y[k]=x;
return true;
}
}
return false;
}
void hungary()
{
int i;
for (i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
ans+=dfs(i);
}
}
int main()
{
memset(opt_y,-1,sizeof(opt_y));
cin>>n>>m;
while (1)
{
scanf("%d%d",&x,&y);
if (x==-1&&y==-1) break;
add(x,y);
}
hungary();
cout<<ans<<endl;
for (i=1;i<=n;i++)
if (opt_x[i]>0) printf("%d %d\n",i,opt_x[i]);//方案
}
```