企业官网建设流程全解析

匈牙利算法（Hungarian Algorithm）通常指用于求解‌二分图最大匹配‌的算法。其正确性证明主要基于图论中的两个核心定理：‌增广路定理‌和‌König定理‌。

以下是严谨的逻辑推导过程：

1. 核心概念定义

• ‌匹配 (Matching)‌：图中一组没有公共端点的边。
• ‌最大匹配 (Maximum Matching)‌：包含边数最多的匹配。
• ‌增广路 (Augmenting Path)‌：设 M 为当前匹配，若路径 P 满足以下条件，则称 P 为关于 M 的增广路：
  1. 起点和终点都是未匹配点（非饱和点）。
  2. 路径上的边交替属于“非匹配边”和“匹配边”。
  3. 由于起点和终点未匹配，且边交替出现，增广路的长度必为奇数，且非匹配边比匹配边多一条。
• ‌对称差 (Symmetric Difference)‌：对于两个匹配 M 和 M′，其对称差 M⊕M′ 是由那些只属于 MM 或只属于 M′M′ 的边组成的集合。

2. 证明逻辑框架

证明分为两个主要部分：

1. ‌充分性‌：如果当前匹配 M 中不存在增广路，则 M 是最大匹配。
2. ‌必要性‌：如果 M 不是最大匹配，则一定存在增广路。（这等价于上述命题的逆否命题，也是算法终止条件的依据）。

第一部分：无增广路 ⇒ 最大匹配

‌定理 (Berge's Lemma)‌：一个匹配 M 是最大匹配，当且仅当图中不存在关于 M 的增广路。

‌证明‌：
假设 M 是当前匹配，且图中不存在关于 M 的增广路。我们要证明 M 是最大匹配。

1. 设 M∗ 是图中的任意一个最大匹配。
2. 考虑集合 S=M⊕M∗（即 M 和 M∗ 的对称差）。
3. 在子图 G′=(V,S) 中，每个顶点的度数最多为 2（因为每个顶点在 M 中最多关联一条边，在 M∗ 中也最多关联一条边）。
4. 因此，G′ 由若干条‌不相交的路径‌和‌环‌组成。
5. 分析这些连通分量的结构：
   • ‌环‌：由于边在 M 和 M∗ 之间交替，环的长度必为偶数。环中来自 M 的边数和来自 M∗ 的边数相等。
   • ‌路径‌：路径上的边也交替属于 M 和 M∗。
     • 如果路径以 M 中的边开始并以 M 中的边结束，或者以 M∗ 开始以 M∗ 结束，则两种边的数量相等。
     • 如果路径以 M∗ 中的边开始并以 M 中的边结束（或反之），则其中一种匹配的边比另一种多一条。
6. ‌关键推论‌：
   • 如果存在一条路径，其来自 M∗ 的边比来自 M 的边多一条，那么这条路径的起点和终点必然都是 M 的未匹配点（因为它们在 M∗ 中被匹配，但在 M 中未被匹配，且路径两端不属于 M）。
   • 这就构成了一条关于 M 的‌增广路‌。
7. ‌矛盾导出‌：
   • 根据前提假设，图中‌不存在‌关于 M 的增广路。
   • 因此，在 S=M⊕M∗ 的所有路径分量中，不可能出现“M∗ 的边比 M 的边多”的情况。
   • 同理，也不可能出现“M 的边比 M∗ 的边多”的情况吗？不，我们需要比较 ∣M∣ 和 ∣M∗∣。
   • 实际上，由于 M∗ 是最大匹配，∣M∗∣≥∣M∣。
   • 如果在任何路径中 M∗M∗ 的边都不多于 MM 的边，且在环中两者相等，那么总边数 ∣M∗∣ 不可能大于 ∣M∣。
   • 既然 ∣M∗∣≥∣M∣ 且 ∣M∗∣≤∣M∣（由无增广路推导出的结构限制，即无法通过异或操作增加 M 的边数而不产生增广路），则必有 ∣M∣=∣M∗∣。
8. ‌结论‌：M 的边数等于最大匹配 M∗ 的边数，故 M 是最大匹配。

第二部分：算法如何保证找到无增广路的匹配

匈牙利算法的核心操作是‌寻找增广路并增广‌。

1. ‌初始状态‌：空匹配 M=∅，显然无增广路（或者说任何单边都是增广路，算法会立即增广）。
2. ‌迭代过程‌：
   • 算法尝试为左部集的每个点寻找增广路。
   • 如果找到增广路 P，则执行 M←M⊕P。新匹配 M′ 的边数比 M 多 1。
   • 如果找不到增广路，则该点无法加入当前匹配，算法继续处理下一个点。
3. ‌终止条件‌：当遍历完所有左部点，且对于每个点都找不到增广路时，算法终止。
4. ‌正确性维持‌：
   • 每次增广后，匹配大小增加 1。
   • 关键在于：‌之前的点是否可能因为后续的增广而重新获得增广路？‌
   • 根据 Berge 定理的证明逻辑，一旦算法确定某个点 u 在当前匹配下没有增广路，并且算法继续处理其他点，即使其他点的匹配状态改变，也不会为 u 创造出新的增广路。这是因为如果存在从 u 出发的增广路，它必然涉及之前已经处理过的点的匹配调整，而这种调整在之前的搜索中已经被穷举或排除（具体实现中通过vis数组标记避免重复搜索，理论上由增广路的性质保证单调性）。
   • 更直观的解释是：匈牙利算法本质上是在构建交错树。如果从 u 出发的交错树无法到达右部未匹配点，说明在该连通分量内，已匹配点数与可访问的右部点数满足 Hall 定理的限制，无法进一步扩展。

3. 补充：König 定理视角

虽然 Berge 定理直接证明了最大匹配与增广路的关系，但匈牙利算法的正确性也常通过 ‌König 定理‌ 来辅助理解其在最小点覆盖中的应用，间接验证其完备性。

• ‌König 定理‌：在二分图中，‌最大匹配数‌ = ‌最小点覆盖数‌。
• 匈牙利算法找到的最大匹配 M，可以通过构造最小点覆盖来验证其最优性。如果算法停止，意味着无法再增加匹配边，此时构建的点覆盖大小等于匹配数，根据 König 定理，这确实是全局最小的点覆盖，从而反证了匹配的极大性。

总结

匈牙利算法的正确性依赖于以下逻辑链：

1. ‌增广路存在性‌：匹配非最大 ⟺ 存在增广路。
2. ‌增广操作有效性‌：沿增广路取反，匹配数严格 +1。
3. ‌终止性‌：有限步内必能找出所有增广路（因为每步匹配数增加，且有上限）。
4. ‌最终状态‌：算法终止时，图中不存在增广路 ⇒ 当前匹配为最大匹配。

#include<iostream> #include<cstdio> #include<cstring> #define _for(i,a,b) for (int i=(a);i<=(b);i++) using namespace std; const int N=1e3+5,M=1e5+5; int n1,n2,m; int e[M],ne[M],h[N],idx; int match[N]; bool vis[N]; inline void c_plus(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); } inline void init(){ memset(h,-1,sizeof(h)); idx=0; } inline void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } bool get(int x){ for (int i=h[x];~i;i=ne[i]){ int j=e[i]; if (vis[j]) continue; vis[j]=true; if (!match[j] || get(match[j])){ match[j]=x; return true; } } return false; } int main(){ init(); c_plus(); int ans=0; cin>>n1>>n2>>m; _for(i,1,m){ int u,v; cin>>u>>v; add(u,v); } _for(i,1,n1){ memset(vis,0,sizeof(vis)); if (get(i)){ ans++; } } cout<<ans<<endl; return 0; }