二分图

染色法

时间复杂度：O(n + m)

算法实现：邻接表存储，dfs一遍，没染色，则染上色

结论1：

一个图是二分图 == 图中不存在奇数环 == 染色法不存在矛盾

p -> q : p 是 q 的充分条件，q 是 p 的必要条件

假设 如上三个条件为 a == b == c

证明1：

  • b 直接推 a 不太容易，所以 b -> c - > a
  • b -> c ：
    • 反证法：假设图中不存在奇数环 但 染色法出现了矛盾。
    • 假设第一个矛盾为两个白色相连，则在该连通块(环)中其他的点一定不存在矛盾，其染色一定为 白-黑-白-黑-……-白，首尾都为白，则符合我们的假设。如此一来，此连通块一定有奇数个点与已知反证法条件相矛盾，则原结论成立。
  • c -> b :
    • 反证法：如果染色的过程中不存在矛盾 但 图中存在奇数环
    • 假设一个环的头为白色，有因为其是奇数环，则其尾一定也为白色，首尾都是白色，所以该图存在矛盾，原结论成立。
  • (b, c) -> a
    • 因为染色法不存在矛盾，则 白黑 相间连接，把白色黑色分别拿出，则构成二分图。
  • a -> (b, c)
    • 反证法：假设一个图是二分图，但图中存在奇数环
    • 奇数环的任意一点出发，则与此点相连的点在另外一个集合中，依此类推，则最后会剩余两个相连的点，但却在同一个集合中，即、此图不是一个二分图，与反证法条件产生矛盾，则原结论成立。

例题：257. 关押罪犯

思路：二分 + 染色法

  • 二分的两段性：假设 x 为最优解，即、x -> 右的边可以构成二分图，若 x 向右移动，仍然可以构成二分图(二分图去掉一些边仍然是二分图，减去一些限制，更自由了)，左边一定不成立，应为 x 为当前的最优解，所以若 check(mid) == true，则当前的图可以构成二分图，向左移动看是否可以构成二分图，若恰好可以构成，则为最优解。

染色法-代码模板：

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
int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，0表示未染色，1表示白色，2表示黑色
 
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j]) // 没染色
        {
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }
 
    return true;
}
 
bool check()
{
    memset(color, 0, sizeof color);

    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i])
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
    
    return flag;
}

匈牙利算法(增广路算法)

时间复杂度：O(n * m)

作用：求二分图最大匹配数目

思路：枚举一边，如果重复，看上一个能不能换

基本概念(针对二分图所言)

  • 匹配：”任意两条边都没有公共端点”的边的集合，被称为图的一组匹配
  • 最大匹配：包含边数最多的一组匹配，被称为二分图的最大匹配
  • 匹配点：在匹配中的点
  • 非匹配点：不在匹配中的点
  • 增广路径：从非匹配点走，非匹配边，匹配边，非匹配边，匹配边，最终通过非匹配边走到了非匹配点，则该路径称为增广路径，增广路径可以使匹配的边数 + 1，匹配的点数 + 2

结论1：

一个匹配是最大匹配 == 不存在增广路径

匈牙利算法-代码模板：

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 n1, n2;  // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;  // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集
                             // 合的边，所以这里只用存一个方向的边
int match[N];  // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];  // 表示第二个集合中的每个点是否已经被遍历过
 
bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
 
    return false;
}
 
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}

二分图的覆盖与独立集

包含的概念：最小点覆盖，最大独立集，最小路径点覆盖(特殊情况：最小路径重复点覆盖)

结论：在二分图中 最大匹配数 == 最小点覆盖 == 总点数 - 最大独立集 == 总点数 - 最小路径点覆盖

基本概念

  • 最小点覆盖：给定一个图，求一个最小的点集 S ，使得图中任意一条边都至少一个端点属于 S。
  • 最大独立集：给定一个图，选出最多的点，使得选出的点之间没有边，等于补图的最大团。
  • 最大团：给定一个图，选出最多的点，使得选出的点之间都有边，等于补图的最大独立集。
  • 最小路径点覆盖(也称为最小路径覆盖): 在有向无环图(DAG)中，用最少的互不相交的路径(点和边都不重复)，将所有点覆盖住。

结论1 ：

在二分图中：最小点覆盖 == 最大匹配数

证明1：

  • 最小点覆盖 >= 最大匹配数:
    • 一条边至少要选一个点，所以 最小点覆盖一定 >= 最大匹配数
  • 最小点覆盖 == 最大匹配数：(证明等号可以成立) (构造)
    • 步骤如下：
    1. 求最大匹配
    2. 从左部每个非匹配点出发，做一遍增广，标记所有经过的点。则，左边所有未被标记的点，和右边所有被标记的点 即为 所求的匹配数。
    3. 可以发现以下的性质：
      1. 左部所有非匹配点，一定被标记，
      2. 右部所有非匹配点一定未被标记(若右边的非匹配点被标记，此路径即为增广路径，非 - …… - 非，所以右部所有非匹配点一定未被标记)
    4. 之后我们只需证明 所有边一定只有一个点被选即可。可以发现一共有四种边，左匹配 - 右匹配， 左非匹配 - 右匹配，左匹配 - 右非匹配，左非匹配 - 右非匹配
    5. 对于 左匹配 - 右匹配 (匹配边) 而言，只有两种情况，同时被标记 和 同时不被标记，右边的点是随左边的点而变化。对于每个匹配而言，则左边所有未被标记的点，一定为匹配点，右边所有被标记的点，一定为匹配点。因此证明，对于每一条匹配边而言，如果左右同时被标记，则选择右边的点计数；如果左右两边同时不被标记，则选择左边的点计数，如此即可保证，对于每个匹配边，必定会选择其中一个点覆盖此边。
    6. 对于 左非匹配 - 右匹配，则右匹配点一定被标记，右匹配点一定被选，左非匹配点一定不被选。
    7. 对于 左匹配 - 右非匹配，则左匹配点一定未被标记，如此则右匹配点一定也未被标记，则我们会选择，左边未被标记的点，而右边的未被标记的点则一定不会被选。
    8. 对于 左非匹配 - 右非匹配，此情况一定不存在，因为此情况表示存在一条增广路径，原图做过最大匹配的算法了，则一定不存在增广路径。
    9. 如此我们即证明了，对于所有边一定有一个点且只有一个点被覆盖。

例题1：376. 机器任务

思路：最小点覆盖 (匈牙利算法求最大匹配数即可)

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

int n, m, k;
bool g[N][N], st[N];
int match[N];

bool find(int x)
{
    for (int i = 1; i < m; i ++ )
        if(!st[i] && g[x][i])
        {
            st[i] = true;
            int t = match[i];
            if(t == 0 || find(t))
            {
                match[i] = x;
                return true;
            }
        }
    
    return false;
}

int main()
{
    while(cin >> n, n)
    {
        memset(g, 0, sizeof g);
        memset(match, 0, sizeof match);
        
        cin >> m >> k;
        while(k -- )
        {
            int t, a, b;
            cin >> t >> a >> b;
            if(!a || !b) continue;
            g[a][b] = true;
        }
        
        int res = 0;
        for (int i = 1; i < n; i ++ )
        {
            memset(st, 0, sizeof st);
            if(find(i)) res ++;
        }
        
        cout << res << endl;
    }
    return 0;
}

结论2：

在二分图中，最大独立集 == 总点数 - 最大匹配数

证明2：

  • 最大独立集 == 去掉最少的点，将所有边都破坏掉，剩余的点的数量 == 总点数 - 最小点覆盖 == 总点数 - 最大匹配数

例题2： 378. 骑士放置

思路：最大独立集

代码如下：

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
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m, k;
PII match[N][N];
bool g[N][N], st[N][N];

int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1}, dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};

bool find(int x, int y)
{
    for (int i = 0; i < 8; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        
        if(a < 1 || a > n || b < 1 || b > m) continue;
        if(st[a][b] || g[a][b]) continue;
        
        st[a][b] = true;
        PII t = match[a][b];
        if(!t.x || find(t.x, t.y))
        {
            match[a][b] = {x, y};
            return true;
        }
    }
    
    return false;
}

int main()
{
    cin >> n >> m >> k;
    
    for (int i = 0; i < k; i ++ )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = true;
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if((i + j) % 2 || g[i][j]) continue;
            memset(st, 0, sizeof st);
            if(find(i, j)) res ++;
        }
        
    cout << n * m - k - res << endl;
    
    return 0;
}

结论3：

在二分图中，最大匹配数 == 总点数 - 最小路径点覆盖

证明3：

  • 结论转化为：最小路径点覆盖 = 总点数 - 最大匹配数
  • 最小路径点覆盖如何实现：
    • 用拆点实现：一个点拆为两个点 入点i 和 出点i ，做完最小路径点覆盖，得到的图是二分图， 入点和出点的集合一定在两侧。
  • 原图的路径 转化到 新图(拆完点的图)中为：新图中的边必然无公共点，原路径对应新图的一个匹配
  • 原图的路径终点 在新图中没有出边，等价于 左部的非匹配点，则原证明可以转化为：让左侧的非匹配点最少(n-m)，等价于 让左侧的匹配点最多(m) 等价于 找最大匹配(m)

结论4：

在二分图中，最大匹配数 == 总点数 - 最小路径重复点覆盖(是最小路径点覆盖的扩展)

证明4：

  • 先求传递闭包，则 原图的最小路径重复点覆盖 可以转化为 新图的最小路径点覆盖(新结论)
  • 证明新结论：
  • 左 -> 右：如果原图的路径有交集，则直接跳过交集的部分，一直跳过，直到无交集位置，如此即为新图上的最小路径点覆盖
  • 左 <- 右：将新图的间接边转化为原图的直接边，则可以成立。

例题： 379. 捉迷藏

思路： 总点数 - 最小重复路径点覆盖 == 最大匹配数

代码如下：

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 210;

int n, m;
bool g[N][N], st[N];
int match[N];

bool find(int x)
{
    for (int i = 1; i <= n; i ++ )
    {
        if(!st[i] && g[x][i])
        {
            st[i] = true;
            int t = match[i];
            if(t == 0 || find(t))
            {
                match[i] = x;
                return true;
            }
        }
    }
    
    return false;
}

int main()
{
    cin >> n >> m;
    
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = true;
    }
    
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                g[i][j] |= g[i][k] & g[k][j];
                
    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        memset(st, 0, sizeof st);
        if(find(i)) res ++;
    }
    
    cout << n - res << endl;
    
    return 0;
}