img

算法学习笔记 - 知乎 (zhihu.com)

匈牙利算法

匈牙利算法主要用于解决一些与二分图匹配有关的问题

二分图（Bipartite graph）是一类特殊的图，它可以被划分为两个部分，每个部分内的点互不相连。下图是典型的二分图。

设 G=(V,E) 是一无向图，若顶点 V 可分割为两个互不相交的子集 (A,B)，且图中的每条边（i,j）所关联的两个顶点 i 和 j 分属这两个不同的顶点集 (i ∈ A,j ∈ B)，则称图 G 为一二分图。

其充要条件是：图 G 中至少存在两个点，且图中所有回路的长度均为偶数。

img

匈牙利算法主要用来解决两个问题：求二分图的最大匹配数和最小点覆盖数。

最大匹配问题

在二分图中最多能找到多少条没有公共端点的边

仔细一点就是，给定二分图 G 中的所有匹配，所含匹配边数最多的匹配，称为这个图的最大匹配，选择最大匹配的问题即为图的最大匹配问题。

具体思路是先连，如果冲突再找找之前的人还能不能连接其他人。

思考一下几个问题罢

要重复判断，不断深入的判断上一个能不能改

这个就需要用到递归了

并且需要记录上一个的左端访问了谁

因此p数组用途就此诞生

并且记录出现的数组也需要

就是bool数组vis，其次存图也可以考虑用邻接矩阵。

三个数组的由来解释清楚了

其他看代码罢

这个代码真的优雅

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
int M, N;          
//M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; 
//邻接矩阵存图
int p[MAXN];         
//记录当前右侧元素所对应的左侧元素
bool vis[MAXN];      
//记录右侧元素是否已被访问过
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
        if (Map[i][j] && !vis[j]) //有边且未访问
        {
            vis[j] = true;                 
            //记录状态为访问过
            if (p[j] == 0 || match(p[j])) 
            //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;    
                //当前左侧元素成为当前右侧元素的新匹配
                return true; 
                //返回匹配成功
            }
        }
    return false; 
    //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}

最小点覆盖问题

我们想找到最少的一些点，使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。

（König定理）

一个二分图中的最大匹配数等于这个图中的最小点覆盖数。

[ZJOI2007] 矩阵游戏

题目描述

小 Q 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 \(n \times n\) 黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：

  • 行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）。
  • 列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）。

游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。

对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小 Q 决定写一个程序来判断这些关卡是否有解。

输入格式

本题单测试点内有多组数据。

第一行包含一个整数 \(T\)，表示数据的组数，对于每组数据，输入格式如下：

第一行为一个整数，代表方阵的大小 \(n\)。 接下来 \(n\) 行，每行 \(n\) 个非零即一的整数，代表该方阵。其中 \(0\) 表示白色，\(1\) 表示黑色。

输出格式

对于每组数据，输出一行一个字符串，若关卡有解则输出 Yes，否则输出 No。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0

样例输出 #1

1
2
No
Yes

提示

数据规模与约定

  • 对于 \(20\%\) 的数据，保证 \(n \leq 7\)。
  • 对于 \(50\%\) 的数据，保证 \(n \leq 50\)。
  • 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 200\)，\(1 \leq T \leq 20\)。

最终状态是（1,1）（2，2）...(n,n)都有一个点

我们把点看成匹配边的话，就是每行和每列都做到了匹配

换言之就是N个行和N个列都有匹配时，一定能转换成最终状态

所以就如S向每行所对应的点连边，每列所对应的点向T连边

每个1的块就是某行和某列的边

再逆过来转换到初始状态，我们发现交换行本质就是交换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
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
int Map[205][205], p[205], vis[205], N, T;
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
    {
        if (Map[i][j] && !vis[j])
        {
            vis[j] = 1;
            if (p[j] == 0 || match(p[j]))
            {
                p[j] = i;
                return true;
            }
        }
    }
    return false;
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= N; ++i)
    {
        memset(vis, 0, sizeof(vis));
        if (match(i))
            cnt++;
    }
    return cnt;
}
int main()
{
    cin>>T;
    while (T--)
    {
        cin>>N;
        memset(p, 0, sizeof(p));
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                cin>>Map[i][j];
        puts(Hungarian() == N ? "Yes" : "No");
    }
    return 0;
}