二分图

二分图指的是顶点可以分为两个独立集U,V的图,即U,V内的顶点不相邻(没有公共边)。
无向图G为二分图的充要条件是G至少有两个顶点,且所有回路的长度都为偶数。

二分图

判定

dfs染色,判定相邻点颜色是否一致

最大匹配

定义

我们将二分图的边分为集合S和M,S ∪ M=E
最大匹配即最多能选择多少条边到S
使得S集合中任意两条边不相邻(没有公共顶点)
显然|S| <= min(|U|,|V|)

匈牙利算法

设当前匹配为S

  • 交替路: 任意相邻的两边一定一条属于S,一条不属于
  • 可增广路: 路径的两端点都为未盖点

匈牙利算法流程

流程图

实现

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
int n;
bool vis[maxn];
vector<int> G[maxn];
int match[maxn];

bool dfs(int u)
{
for(int i = 0; i < G[u].size();++i)
{
int v = G[u][i];
if(!vis[v])
{
vis[v] = 1;
int t = match[v]; match[v] = u;
if(t == -1 || dfs(t)) return true;
match[v] = t;
}
}
return false;
}

int solve()
{
int ans = 0;
memset(match,-1,sizeof(match));
for(int i = 1;i <= n;++i)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
return ans/2;
}

复杂度 $O(nm)$

结论

  • 最小点覆盖: 一个最小的点集,使所有的边至少有一个端点在集合内
  • 最小边覆盖: 一个最小的边集,使所有的点都与集合内的边邻接
  • 最大独立集: 一个最大的点集,这些点两两之间没有边相连
  • 最大匹配 = 最小点覆盖
  • 最少小边覆盖 = 最大独立集 = 顶点数 - 最大匹配

最大权匹配

  • 完备匹配: S为G的一个最大匹配,若|S| = min(|U|,|V|),则S为完备匹配
  • 完美匹配: 若|S| = |U| = |V|,则S为完美匹配
  • 最佳匹配: 带权二分图的最大权/最小权匹配
  • 二分图的最佳匹配一定是完备匹配

KM算法

求二分图的最大权匹配

  • 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
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
87
88
89
90
91
92
93
94
const int maxn = 500+5;
const int INF = 0x3f3f3f3f;

struct KM
{
int n;
vector<int> G[maxn];
int W[maxn][maxn];
int Lx[maxn],Ly[maxn];
bool visx[maxn],visy[maxn];
int link[maxn];
int slack[maxn];

void init(int n)
{
this->n = n;
for(int i = 0;i < n;++i) G[i].clear();
memset(W,0,sizeof(W));
}

void addEdge(int u,int v,int w)
{
G[u].push_back(v);
W[u][v] = w;
}

bool match(int x)
{
visx[x] = true;
for(int i = 0;i < G[x].size();++i)
{
int y = G[x][i];
if(visy[y]) continue;
int t = Lx[x] + Ly[y] - W[x][y];
if(t == 0)
{
visy[y] = true;
if(link[y] == -1 || match(link[y]))
{
link[y] = x;
return true;
}
}
else if(slack[y] > t)
slack[y] = t;
}
return false;
}

void update()
{
int a = INF;
for(int i = 0;i < n;++i)
if(!visy[i] && a > slack[i])
a = slack[i];

for(int i = 0;i < n;++i)
{
if(visx[i]) Lx[i] -= a;
if(visy[i]) Ly[i] += a;
else slack[i] -= a;
}
}


int getRes()
{
for(int i = 0;i < n;++i)
{
Lx[i] = -INF;
for(int j = 0;j < G[i].size();++j)
Lx[i] = max(Lx[i],W[i][G[i][j]]);
Ly[i] = 0;
link[i] = -1;
}
for(int i = 0;i < n;++i)
{
memset(slack,INF,sizeof(slack));
while(1)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(match(i)) break;
else update();
}
}

int res = 0;
for(int i = 0;i < n;++i)
if(link[i] != -1)
res += W[link[i]][i];
return res;
}
};

复杂度 $O(n^3)$

转化

最小权匹配

权值取相反数,跑KM,答案再取相反数

非完备

把不存在的边权值赋为0(-INF)

或者用费用流解决
附加源点S,与集合U中每个点添加一条弧,容量为1,费用为0
集合V中每个点添加一条弧到附加汇点T,容量为1,费用为0
其余边容量为1,费用为边权

稳定婚姻问题

有n对男女,每人按照其对异性的喜好程度按1-n排序,安排男女结婚
对于其中的任意两对夫妇 (m,w)(m',w'),不存在
m对w’的喜好程度大于w,且w对m’的喜好程度大于m
就称这是一个稳定婚姻匹配

算法很简单,就是男生主动求婚,女生不断拒绝
男生按照喜好程度的顺序主动求婚,而女生对于当前求婚的男生
若喜好程度高于之前订婚的男生(或尚未订婚),则订婚
若有订婚的男生被抛弃,则加入队列继续之前的顺序求婚

p.s. 最后结果是男生有可能娶到自己可能娶到的最好的妻子,而女生只能嫁给自己可能嫁到的最差的丈夫2333