匈牙利树的了解
“匈牙利树”（Hungarian Tree）这个词听起来很专业，但它其实就是指在“匈牙利算法”中，为了寻找增广路而临时构建出来的一棵“搜索树”。
你提供的图片里描述的“最后会扩展出一颗匈牙利树”，指的就是一次失败的搜索尝试所遍历过的所有节点和路径。
我们还是用“相亲配对”的例子来解释，并严格对应你图中的描述：
假设我们有男生（U）和女生（V），我们想给男生找对象。
-
算法目标： 逐个检查未覆盖的男生（X结点），看能不能给他找到一个增广路。
-
搜索方式： 使用深度优先搜索（DFS）。
“匈牙利树”的构建过程（一次DFS）
我们开始为未覆盖的男生 U1 找增广路。
-
树根 (Root)：
-
U1是“未覆盖点”，他就是这棵“匈牙利树”的树根。
-
-
扩展第一层 (走“非匹配边”)：
-
我们看
U1认识谁。假设U1认识V1和V2。 -
我们先尝试
V1。我们走了 [非匹配边](U1, V1)。 -
V1成为U1的子节点。 -
树：
U1 -> V1
-
-
扩展第二层 (走“匹配边”)：
-
我们检查
V1的状态。 -
情况A（失败）：
V1已经有对象了，她和U2匹配（U2就是你图中说的left[V1]）。 -
算法规定（如图中所示），我们必须沿着 [匹配边]
(V1, U2)走回去，去找U2。 -
U2成为V1的子节点。 -
树：
U1 -> V1 -> U2
-
-
扩展第三层 (走“非匹配边”)：
-
现在我们从
U2出发，看他除了V1（V1已经在这棵树里了，不能往回走）还认识谁。 -
假设
U2还认识V3。 -
我们走了 [非匹配边]
(U2, V3)。V3成为U2的子节点。 -
树：
U1 -> V1 -> U2 -> V3
-
-
搜索结束（失败）：
-
我们检查
V3的状态。 -
情况B（失败）：
V3也有对象了，她和U4匹配。 -
我们必须沿着 [匹配边]
(V3, U4)走回去，去找U4。 -
情况C（失败）：
U4没有任何其他“非匹配边”可以走了（他认识的人都在这棵树里了）。 -
回溯 (Backtrack)：
-
从
U4退回V3。 -
从
V3退回U2。U2也没有其他路可走。 -
从
U2退回V1。 -
从
V1退回U1。
-
-
尝试另一条路： 我们回到树根
U1，尝试他认识的V2。 -
情况D（全失败）： 假设
V2也匹配了，并且沿着V2走下去的所有路径最终都失败了（都撞墙了，找不到任何一个“未覆盖”的女生）。
-
最终，我们从 U1 出发的所有“交替路”都尝试完了，也没有找到一个“未覆盖”的女生。
什么是匈牙利树？
上面这个从 U1 出发，遍历过的所有节点和路径（包括 U1->V1->U2->V3... 和 U1->V2->...），所组成的这棵“交替路径”搜索树，就叫做“匈牙利树”。
你图中的“最后会扩展出一颗匈牙利树”，意思就是：
“我们从 U 点出发的DFS搜索失败了，这次搜索所构建的这棵树，就是匈牙利树。”
为什么这棵树很重要？
-
这棵树代表了从
U1出发的所有“增广”可能性。 -
如果这棵树构建完毕（即DFS搜索结束）都没有找到增广路，就意味着：从
U1出发，已经不可能找到增广路了。 -
正如你图中最后一句所说：“则以后再也不从 u 出发找增广路”。算法就会把
U1标记为“已检查”，然后换下一个未覆盖的男生（比如U5），从U5开始，构建一棵全新的匈牙利树，再次重复这个搜索过程。 -
注意： 如果搜索成功了（比如在第3层找到了未覆盖的
V3），那么U1 -> V1 -> U2 -> V3就是一条增广路。我们立刻“反转”它，然后这次搜索就结束了，我们不会继续扩展这棵树。我们会直接去找下一个未覆盖的男生。
匈牙利算法的实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=600+5;
bool line[maxn][maxn];
//line[x][y]=true表示x号女生喜欢y男生(边）
int boy[maxn];
//存储y号男生匹配边另一端的匹配点女生，如果是未覆盖点则为0
bool use[maxn];
//存储y号男生是否在这条交替路上被使用过,男生是否被别人喜欢
int k,n,m;
bool dfs(int x)
{
for(int j=1;j<=m;j++)
{
if(line[x][j]&&!use[j])
{
use[j]=true;
if(!boy[j]||dfs(boy[j]))
{
//满足上面的判断语句说明找到了增广路
//即终点是未覆盖点的交替路
boy[j]=x;
return true;
}
}
//该条路不是增广路
}
return false;
}
int main()
{
while(cin>>k)
{
if(!k)
break;
cin>>n>>m;
int x,y;
int ans=0;
memset(line,false,sizeof(line));
memset(boy,0,sizeof(boy));
while(k--)
{
cin>>x>>y;
line[x][y]=true;
}
for(int i=1;i<=n;i++)
{
memset(use,false,sizeof(use));
if(dfs(i))
ans++;
}
cout<<ans<<endl;
}
return 0;
}
代码的理解解释
想象一下，你就是那个月老，你的任务是给一群女生和一群男生牵红线，目标是让总配对数最多。
剧本：月老的“花名册”和“工具”
在我们开始之前，我们先看看月老（也就是程序）手上的几个关键“花名册”（也就是变量）：
-
bool line[maxn][maxn];-
翻译： 这是你的**“姻缘可能性”**记录册。
-
line[x][y] = true的意思是：“女生x对男生y有好感（可以连线）”。 -
line[x][y] = false的意思是：“他俩不认识（不能连线）”。 -
这是一个布尔（bool）类型的二维数组，
bool意思是它只存true(真) 或false(假)。
-
-
int boy[maxn];-
翻译： 这是**“男生匹配状态”**表。
-
boy[y] = x的意思是：“男生y目前正和女生x牵着红线（已匹配）”。 -
boy[y] = 0的意思是：“男生y目前是单身（未覆盖点）”。 -
这是我们算法的核心数据，记录了“当前”的匹配结果。
-
-
bool use[maxn];-
翻译： 这是你手上的一个**“临时勿扰”**便签。
-
这个便签非常重要！它只在一次“寻找增广路”的尝试中使用。
-
use[j] = true的意思是：“在这一轮的尝试中，我已经找过男生j了，别再重复找他，不然会绕圈子。” -
当你开始为下一个女生寻找增广路时，你会撕掉这张旧便签，换一张全新的、空白的便签。
-
-
int k, n, m;-
翻译：
n= 女生总数，m= 男生总数，k= “姻缘可能性”的总条数。
-
核心剧情：dfs(int x) 函数
这个函数是整个算法的灵魂。dfs 的意思是“深度优先搜索”，我们可以把它翻译成：“月老为女生 x 拼命寻找（或腾出一个）配对名额”。
bool dfs(int x) 的意思是：这个函数在执行完后，会给你一个答案（bool 类型）：
-
返回
true：“成功了！我为女生x找到了一条增广路，总配对数+1！” -
返回
false：“失败了！我从女生x出发试了所有可能，都找不到增广路。”
dfs(int x) 剧情分解：
C++
bool dfs(int x) // 月老开始为女生 x 忙活
{
// 月老拿出“姻缘可能性”记录册，开始查看女生 x 喜欢的男生
// 从男生 1 号（j=1）一直看到最后一个（j=m）
for(int j=1;j<=m;j++)
{
// 月老查看男生 j，需要满足两个条件：
// 1. line[x][j]：女生 x 必须喜欢男生 j
// 2. !use[j]：在“这一轮”尝试中，男生 j 还没有被问过
if(line[x][j]&&!use[j])
{
// 月老：“好了，我现在要问男生 j 了，
// 先在‘临时勿扰’便签上记下他。”
use[j]=true;
// 月老去问男生 j：“你愿意和女生 x 在一起吗？”
// 现在有两种可能：
// 1. !boy[j]
// 翻译：如果 boy[j] == 0，即“男生 j 是单身！”
// 2. dfs(boy[j])
// 翻译：如果男生 j 不是单身（假设他和女生 k 在一起，
// 即 boy[j] == k），月老就会去找女生 k，
// 然后对她说：“你（女生 k）能不能换个对象？
// （即执行 dfs(k)）”
// 如果 dfs(k) 返回 true，说明女生 k 成功换了对象，
// 那么男生 j 就“腾”出来了！
if(!boy[j]||dfs(boy[j]))
{
// 两种情况只要满足一个（“||”就是“或”的意思），
// 月老就找到了增广路！
// 月老：“太好了！男生 j，你现在归女生 x 了！”
// （这就是“反转”增广路，更新匹配）
boy[j]=x;
// 月老向上级（上一层调用）汇报：“成功！”
return true;
}
}
// 如果 if(line[x][j] && !use[j]) 不满足，
// 或者 if(!boy[j] || dfs(boy[j])) 不满足
// （即这条路是死胡同）
// 月老会继续 for 循环，看下一个男生 j+1
}
// 如果 for 循环走完了（女生 x 喜欢的所有男生都试过了）
// 还是没有 return true
// 月老只好向上级汇报：“失败！女生 x 找不到对象。”
return false;
}
主线故事：main() 函数
这是月老办公室的“主程序”。
C++
int main()
{
// 只要还在输入 k（姻缘条数）
while(cin>>k)
{
if(!k) // 如果 k=0，不干了，下班
break;
// 读入女生数 n 和 男生数 m
cin>>n>>m;
int x,y; // 临时变量，用来读入
int ans=0; // 最终的“总配对数”，初始化为 0
// 月老开始“清场”，为新一轮配对做准备
// 把“姻缘可能性”记录册全擦掉
memset(line,false,sizeof(line));
// 把“男生匹配状态”表全清零（所有男生都单身）
memset(boy,0,sizeof(boy));
// 循环 k 次，读入 k 条“姻缘可能性”
while(k--)
{
cin>>x>>y; // 读到：女生 x 喜欢 男生 y
line[x][y]=true; // 在记录册上记一笔
}
// --- 月老开始正式工作 ---
// 月老决定，按顺序从 1 号女生到 n 号女生，
// 挨个为她们尝试寻找（或腾出）一个对象
for(int i=1;i<=n;i++)
{
// 关键一步！
// 在为女生 i 开始新一轮尝试之前，
// 月老撕掉了上一张“临时勿扰”便签
// 换上一张全新的、空白的便签
// （因为为 i 找对象时，不应该被为 i-1 找对象时的
// 路线所干扰）
memset(use,false,sizeof(use));
// 月老开始执行核心任务：
// “为女生 i 拼命寻找配对名额！”
if(dfs(i))
{
// 如果 dfs(i) 返回了 true，
// 说明月老成功了！总配对数+1
ans++;
}
// 如果 dfs(i) 返回 false，说明女生 i 这次没成功
// （她可能在之前的轮次里被别人“腾”走了对象）
// 没关系，ans 不增加，继续看下一个女生
}
// 当 1 号到 n 号女生都尝试完毕
// 月老宣布：“工作完成！最大配对数是：”
cout<<ans<<endl;
}
return 0; // 程序结束
}
总结
这个代码就是匈牙利算法的完美实现：
-
main函数里的for(int i=1; i<=n; i++)循环，就是挨个尝试为每个女生（X结点）找对象。 -
dfs(i)函数，就是从女生i出发，寻找增广路的过程。 -
memset(use, false, ...)放在for循环内部，是保证每次寻找增广路都是一次全新的“匈牙利树”搜索。 -
if(!boy[j] || dfs(boy[j]))这个判断，完美实现了“交替路”：-
!boy[j]：找到了未覆盖的 V 结点（男生），增广路终点。 -
dfs(boy[j])：沿着 V 结点的匹配边，去找它对应的 U 结点（女生），并让她“让位”。
-
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
38
0- 0
已为社区贡献1条内容
所有评论(0)