原创建时间：2018-07-06 21:36:45

二分图

概念

设图是一个无向图，若顶点集合可分割为两个互不相交的子集和，且图中每条边连接的顶点一个在中，一个在中，则称是一个二分图。

判定

若某一图是联通的，

1
2
3

1. 任选一个点V作为顶点，定义距离标号为0
2. 将V的邻接点标号设为1，接着将它的未标号的邻接点的标号设为2，以此类推 
3. 将所有标号为奇数的点归为X，标号为偶数的点归为Y

以上内容可以采用BFS完成

依次检查每一条边，看看是否满足顶点一个在中，一个在中

若某一图不连通，就在每个联通块里进行判定

二分图匹配

定义

给定一个二分图，在的子图中，的边集中的任意两条边都不依附于同一个顶点，则称是一个匹配。

图中蓝色的边是数量为2的匹配

oQPHl.png

最大匹配 & 完全匹配

选择边数最大的子图称为「二分图的最大匹配问题」

如果一个匹配中图的每一个顶点都和某条边相关联，则称此匹配为「完全匹配」（或「完备匹配」）

图中为一个完全匹配

oQa4J.png

增广路径

定义

设为二分图已匹配边的集合，若是上其中一条联通两个未匹配顶点的路径（起点在部，终点在部），且属的边和不属的边在上交替出现，则称为相对于的一条增广路径

寻找增广路

设为二分图所有已匹配边的集合，

如图，蓝色为在里的边，黄色为不在里的边

oW9gr.png

从到找一条路径：

$
x_4 \rightarrow y_3 \rightarrow x_2 \rightarrow y1 \rightarrow x1 \rightarrow y2
$

这条路径就是「增广路径」

其中属于的边有：

不属于的边有：

显然，不属于的边比属于的边要多一条

将这条增广路上的边全都「反色」，如图

oWBQY.png

可以发现，匹配仍然合法，但是匹配数多了一对

另外，单独的一条连接两个未匹配点的边显然也是增广路   

那么可知，当不能再找到增广轨时，就得到了一个「最大匹配」，这就是匈牙利算法的基本思路

增广路径性质

由增广路的定义可以推出下述三个结论：

1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M，因为两个端点分属两个集合，且未匹配。
2. P经过取反操作可以得到一个更大的匹配M’。
3. M为G的最大匹配当且仅当不存在相对于M的增广路径。

匈牙利算法

用增广路求最大匹配（称作匈牙利算法，匈牙利数学家Edmonds于1965年提出）

算法步骤

1. 置为空
2. 找出一条增广路，通过取反操作获得更大的匹配代替
3. 重复2直到找不出增广路

找增广路径的算法

我们采用DFS的办法找一条增广路径：

从X部一个未匹配的顶点u开始，找一个未访问的邻接点v（v一定是Y部顶点）。

对于，分两种情况：

1. 如果未匹配，则已经找到一条增广路
2. 如果已经匹配，则取出的匹配顶点(一定是部顶点)，边目前是匹配的，根据“取反”的想法，要将改为未匹配，设为匹配，能实现这一点的条件是看从为起点能否新找到一条增广路径。如果行，则就是一条以为起点的增广路径。

伪代码

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
寻找从 出发的增广路径
返回 表示成功匹配， 反之
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
  的邻接点
        未访问过
            标记 被访问过
            未被匹配 或者 的匹配点
                标记 的匹配点为 ， 的匹配点为
               
           
       
  

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int ans[MAXN];
// ans 表示 Y 集合中每个顶点的匹配点

bool vis[MAXN];

memset(px, -1, sizeof px);
// 用 -1 表示没有匹配

bool DFS(int u) {
    for (int e = head[u]; e; e = edge[e].next) {
        int now = edge[e].now;
        if (!vis[now]) {
            vis[now] = true;
            if (px[now] == -1 || DFS(px[now])) {
                px[u] = now;
                // 为了方便，可以只标记 Y 到 X
                return true;
            }
        }
    }
}

《HDU2063 过山车》题解

题目描述

RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？

Input/Output 格式 & 样例

Input

输入数据的第一行是三个整数，分别表示可能的组合数目，女生的人数，男生的人数。$0<K<=1000,
1<=N,M<=500KA_iB_j0$结束输入。

Output

对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。

Sample Input

1
2
3
4
5
6
7
8

6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0

Sample Output

1

3

解析

「每个女生必须找个个男生做partner和她同坐」

好了，可以看出这是匹配问题，问你如何匹配

「Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner」

这句话告诉了我们如何建边：

1
2
3

把所有女生的顶点放到集合X中，所有男生的顶点放到集合Y中，
从Rabbit分别建一条到XHD的边和一条到PQK的边，
从Grass分别建一条到linle的边和一条到LL的边……

那么显然这就是一个二分图，而本题要求的就是这个二分图的最大匹配

又是一道模板题

代码实现

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

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 500 + 10;

int t[MAXN][MAXN], map[MAXN];
bool vis[MAXN];

int k, m, n;

bool dfs(int u) {
    for (int i = 1; i <= n; ++i) {
        if (t[u][i] && !vis[i]) {
            vis[i] = true;
            if (!map[i] || dfs(map[i])) {
                map[i] = u;
                return true;
            }
        }
    } 
    return false;
}

int main(int argc, char *const argv[]) {
    while (scanf("%d %d %d", &k, &m, &n), k != 0) {
        memset(t, 0, sizeof(t));
        memset(vis, 0, sizeof(vis));
        memset(map, 0, sizeof(map));
        for (int i = 0; i < k; ++i) {
            int x, y;
            scanf("%d %d", &x, &y);
            t[x][y] = 1;
        }
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            memset(vis, 0, sizeof(vis));
            if (dfs(i)) ++ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}