我们最近来学点 二分图吧
什么是二分图
通俗来讲：只存在由一个集合中的点指向另一个集合中的点的边。（也就是说两个集合中点不互通）
二分图的最大匹配
匈牙利算法：
P3386 【模板】二分图最大匹配
中介卖房子：
#include <bits/stdc++.h>
using namespace std;
int ne[50010],ver[50010],head[50010];
int yuyue[510],biao[510];
int tot=0;
void add(int x,int y){
ver[++tot]=y;
ne[tot]=head[x];
head[x]=tot;
}
bool zhongjie(int x){//客户
for(int i=head[x];i;i=ne[i]){
int y=ver[i];
if(!biao[y]){//看看想要房子有没有被订购
biao[y]=1;
if(!yuyue[y] || zhongjie(yuyue[y])){//该买家还没匹配 或者 已经匹配看能不能更换其他房子
yuyue[y]=x;
return true;
}
}
}
return false;
}
int main(){
int n,m,e;//买家 房子 关系总数
cin>>n>>m>>e;
for(int i=1;i<=e;i++){
int x,y;
cin>>x>>y;
add(x,y);//把买家 与 想要的房子匹配
}
int ticheng=0;
for(int i=1;i<=n;i++){
memset(biao,0,sizeof(biao);
if(zhongjie(i)){
ticheng++;
}
}
cout<<ticheng<<endl;
return 0;
}
用二维数组 <邻接矩阵>
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int g[N][N];
int vis[510],linker[510];
int m;
bool dfs(int x){
for(int i=0;i<m;i++){
if(!vis[i] && g[x][i]){
vis[i]=1;
if(linker[i]==-1 || dfs(linker[i])){
linker[i]=x;
return true;
}
}
}
return false;
}
int main(){
int n,e;
cin>>n>>m>>e;
for(int i=1;i<=e;i++){
int x,y;
cin>>x>>y;
g[x][y]=1;
}
int cnt=0;
memset(linker,-1,sizeof(linker));
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)){
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
最小顶点覆盖
用最少的点覆盖所有的边 == 二分图最大匹配数
Machine Schedule
注意点： At the beginning they are both work at mode_0. 开始就在0，由 0 指向任意一条边cnt 不加 1
#include <bits/stdc++.h>
using namespace std;
int m;
const int N=5e4+10;
int g[N][N];
int vis[510];
int linker[510];
int dfs(int x){
for(int i=1;i<=m;i++){
if(g[x][i] && vis[i]==0){
vis[i]=1;
if(linker[i]==-1 || dfs(linker[i])){
linker[i] = x;
return true;
}
}
}
return false;
}
int main(){
int n,e;
while(scanf("%d",&n)!=EOF){
if(n==0) break;
cin>>m>>e;
memset(g,0,sizeof(g));
while(e--){
int op,x,y;
cin>>op>>x>>y;
if(x>0 && y>0)
g[x][y] = 1;
}
int cnt=0;
memset(linker,-1,sizeof(linker));
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
DAG图的最小路径覆盖
最少的路覆盖所有的点
用尽量少的不相交的简单路径覆盖有向无环图（DAG）的所有顶点
DAG图的最小路径覆盖 == 节点数-最大匹配数
#include <bits/stdc++.h>
using namespace std;
int m,e;
const int N=5e4+10;
int g[N][N];
int vis[510];
int linker[510];
int dfs(int x){
for(int i=1;i<=m;i++){
if(g[x][i] && vis[i]==0){
vis[i]=1;
if(linker[i]==-1 || dfs(linker[i])){
linker[i] = x;
return true;
}
}
}
return false;
}
int main(){
int n;
cin>>n;
while(n--){
cin>>m>>e;
memset(g,0,sizeof(g));
while(e--){
int x,y;
cin>>x>>y;
g[x][y] = 1;
}
int cnt=0;
memset(linker,-1,sizeof(linker));
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) cnt++;
}
cout<<m-cnt<<endl;
}
return 0;
}
二分图的最大独立集
二分图的最大独立集 == 节点数-最小顶点覆盖
HDU 1068 Girls and Boys
题意：求出不能组成对的最少人数
用匈牙利算法求出最大的匹配数
该题没有给出哪些为男哪些为女，所以就把一人拆成两人来算，最终匹配的数目要/2；
#include <bits/stdc++.h>
using namespace std;
int n;
int g[1005][1005];
int vis[1005];
int linker[1005];
int dfs(int x){
for(int i=0;i<n;i++){
if(g[x][i] && vis[i]==0){
vis[i]=1;
if(linker[i]==-1 || dfs(linker[i])){
linker[i] = x;
return true;
}
}
}
return false;
}
int main(){
while(cin>>n){
memset(g,0,sizeof(g));//放在读入之前 否则每次读入被清空 （和linker类似）
int m,e,x;
for(int i=0;i<n;i++){
scanf("%d: (%d)",&m,&e);
for(int j=0;j<e;j++){
cin>>x;
g[m][x] = 1;
}
}
int cnt=0;
memset(linker,-1,sizeof(linker));
for(int i=0;i<n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) cnt++;
}
cout<<n-cnt/2<<endl;
}
return 0;
}
