算法学习笔记（匈牙利算法）

本文主要是介绍算法学习笔记（匈牙利算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

匈牙利算法可以求解二分图的最大匹配问题（二分图：如果无向图 $G = (V, E)$ 的所有点可以分为两个集合 $V_1、V_2$ ，所有的边都在 $V_1$ 和 $V_2$ 之间，而 $V_1$ 或 $V_2$ 的内部没有边，称 $G$ 是一个二分图。）。

直接引用例题进行解释。

例题：情人节

题目描述

温馨提示：2月14日是第一台通用计算机在宾夕法尼亚大学诞生的日子，在这个特殊的日子，请多花点时间陪陪你的电脑。

现在有 $n$ 个男孩（ $1 \sim n$ 编号）， $m$ 个女孩（ $1 \sim m$ 编号），如果一对男女之间存在暧昧关系，那么他俩就有可能成为情侣，现在给出 $k$ 对暧昧关系，请问最多可以产生多少对情侣？

输入描述

第一行三个整数 $n, m, k$ 。 $\leq n,m \leq 3 \times 10^3,1 \leq k \leq 10^4)$

接下来 $k$ 行，每行表示一个暧昧关系 $x, y$ ，表示男孩 $x$ 和女孩 $y$ 存在暧昧关系。 $\leq x \leq n,1 \leq y \leq m)$ 。

输出描述

一行输出结果。

输入样例

输出样例

解释

至多可以产生三对情侣，分别是 $[1, 3], [2, 1], [3, 4]$ 。

匈牙利算法的流程是这样的：

对访问到的男孩，如果他的暧昧对象没有被分配情侣，那么直接将他们两配对。如果当前访问到的暧昧对象被分配了对象，那么他会试图拆开他们，而被访问的暧昧对象的情侣则会找他其他的暧昧对象试图进行配对，往复下去，如果能结对，那么皆大欢喜。如果不行，则返回到第一层那里，去看他的下一个暧昧对象是否已经和他人配对。

原理是一个贪心的思想：当一个节点匹配后，不改变他已经匹配的状态，只可能更换他的匹配对象，从而实现全局的最大匹配。

采用 $df s$ 来实现。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 9;vector<int> g[N];
//记录时间戳，防止一次访问时走重复路径，
//代替vis的功能，如果使用vis数组则需要多次清空vis数组
int dfn;        
int p[N];
int vis[N];bool dfs(int x)
{for(auto &y : g[x]){//当前男孩已经被访问过了if(vis[y] == dfn) continue;     vis[y] = dfn;//如果女孩未经匹配或者下一个男孩可以更改匹配对象if(!p[y] || dfs(p[y]))      {p[y] = x;       //进行匹配return true;}}return false;
}void solve()
{int n, m, k; cin >> n >> m >> k;for(int i = 1; i <= k; ++i)     //存图{int x, y; cin >> x >> y;g[x].push_back(y);}int ans = 0;        //存答案for(int i = 1; i <= n; ++i){dfn++;if(dfs(i)) ans++;}cout << ans << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1;while(_--) solve();return 0;
}