二分图总结

二分图总结

模版

hungary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int g[maxn][maxn],linker[maxn];
bool used[maxn];
bool dfs(int u){
for(int i=0;i<m;i++){
if(g[u][i] && !used[i]){
used[i]=true;
if(linker[i]==-1 || dfs(linker[i])){
linker[i]=u;
return true;
}
}
}
return false;
}
int hungary(){
int ans=0;
mm(linker,-1);
for(int i=0;i<n;i++){
mm(used,0);
if(dfs(i)) ans++;
}
return ans;
}

下标从0开始 n和m分别记录2个集合的点数

km

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int nx,ny;
int g[maxn][maxn];
int linker[maxn],lx[maxn],ly[maxn];
int slack[maxn];
bool visx[maxn],visy[maxn];
bool dfs(int x){
visx[x]=true;
for(int y=0;y<ny;y++){
if(visy[y]) continue;
int tmp=lx[x]+ly[y]-g[x][y];
if(tmp==0){
visy[y]=true;
if(linker[y]==-1 || dfs(linker[y])){
linker[y]=x;
return true;
}
}
else slack[y]=min(slack[y],tmp);
}
return false;
}
int km(){
mm(linker,-1),mm(ly,0);
for(int i=0;i<nx;i++){
lx[i]=g[i][0];
for(int j=1;j<ny;j++) lx[i]=max(lx[i],g[i][j]);
}
for(int i=0;i<nx;i++){
fill(slack,slack+ny,inf);
while(1){
mm(visx,false),mm(visy,false);
if(dfs(i)) break;
int d=inf;
for(int j=0;j<ny;j++){
if(!visy[j]) d=min(d,slack[j]);
}
for(int j=0;j<nx;j++){
if(visx[j]) lx[j]-=d;
}
for(int j=0;j<ny;j++){
if(visy[j]) ly[j]+=d;
else slack[j]-=d;
}
}
}
int ans=0;
for(int i=0;i<ny;i++){
if(linker[i]!=-1) ans+=g[linker[i]][i];
}
return ans;
}

下标从0开始 nx和ny分别记录2个集合的点数

相关结论

二分图判定
dfs交叉染色法
转跳链接

最小边覆盖
最小边覆盖 = 最大独立集 = 顶点数 - 最大匹配数
这是二分图的基本性质 需要满足原图是二分图
这里的最大匹配数是在原二分图上进行的
最大匹配用匈牙利算法

最小路径覆盖
最小路径覆盖=顶点数-最大匹配数
最小路径覆盖和最小边覆盖不同,不要求给的图是二分图,而是要求是有向图,不能有环,然后根据原图构造二分图
构造方法是拆点 最大匹配用dinic 转跳链接
也可以用匈牙利求匹配

最小顶点覆盖
最小顶点覆盖=最大匹配数
要求原图是二分图 使用匈牙利算法

最大带权独立集合
最大带权独立集合=总权值-最小顶点覆盖=总权值-最大匹配数
拆点 用dinic求最大匹配数
转跳链接

带权最小k路径覆盖
网络流
转跳链接

最大团
最大团顶点数 = 原图补图的最大独立集顶点数 = 补图顶点数-补图最大匹配数
最大匹配数用匈牙利算法

uva 12549

题目要求

紫书P381

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define maxn 5050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,r,c,n,m,num;
int mp[maxn][maxn];
int g[maxn][maxn],linker[maxn];
bool used[maxn];
struct node{
int x,y;
}a[maxn][maxn];
bool dfs(int u){
for(int i=0;i<m;i++){
if(g[u][i] && !used[i]){
used[i]=true;
if(linker[i]==-1 || dfs(linker[i])){
linker[i]=u;
return true;
}
}
}
return false;
}
int hungary(){
int ans=0;
mm(linker,-1);
for(int i=0;i<n;i++){
mm(used,0);
if(dfs(i)) ans++;
}
return ans;
}
void build(){
int row=-1,col=-1;
for(int i=1;i<=r;i++){
bool flag=true;
for(int j=1;j<=c;j++){
if(mp[i][j]==1){
if(flag) row++;
a[i][j].x=row;
flag=false;
}
if(mp[i][j]==2) flag=true;
}
}
for(int j=1;j<=c;j++){
bool flag=true;
for(int i=1;i<=r;i++){
if(mp[i][j]==1){
if(flag) col++;
a[i][j].y=col;
flag=false;
}
if(mp[i][j]==2) flag=true;
}
}
n=row+1,m=col+1;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
if(mp[i][j]==1) g[a[i][j].x][a[i][j].y]=1;
}
}
}
int main(){
// freopen("input.txt","r",stdin);
scanf("%d",&t);
while(t--){
mm(mp,0),mm(g,0),mm(a,0);
scanf("%d%d",&r,&c);
scanf("%d",&num);
while(num--){
int x,y;
scanf("%d%d",&x,&y);
mp[x][y]=1; //重要
}
scanf("%d",&num);
while(num--){
int x,y;
scanf("%d%d",&x,&y);
mp[x][y]=2; //障碍
}
build();
printf("%d\n",hungary());
}
return 0;
}

思路

本题可以转换为最小顶点覆盖 二分图的最小顶点覆盖=二分图最大匹配数
重在建图(若没有障碍更简单 有障碍只需要领取一行或一列即可) 然后直接跑hungary即可
初始化row和col为-1 遇到重要位置记录下行或者列 若遇到障碍物 行和列需要额外加1 代表需要新的机器人
row是从行开始 col是从列开始 n和m更新2个集合的点数
最后的二分图相当于:第一个集合代表行 第二个集合代表列 某个机器人可以守护某一行或者某一列 对应的行列相连
最小顶点覆盖即为选择最少的机器人能够守护到所有的行或列

HDU 1150

转跳链接

HDU 2255

转跳链接

HDU 1533

转跳链接

文章目录
  1. 1. 二分图总结
    1. 1.1. 模版
      1. 1.1.1. hungary
      2. 1.1.2. km
    2. 1.2. 相关结论
    3. 1.3. uva 12549
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 1150
    5. 1.5. HDU 2255
    6. 1.6. HDU 1533
|