百度作业网二分图匹配 匈牙利算法
来源：学生作业帮 编辑：百度作业网作业帮 分类：综合作业 时间：2024/08/09 23:25:36
二分图匹配 匈牙利算法
我现在已经看懂了那个find函数,但是现在我不明白为什么在主程序中调用这样的话就可以实现二分图匹配?
ans:=0;
for i:=1 to n do
if find(i)then inc(ans);
writeln(ans);
假设i=1的时候匹配了一个点K,后来1-k这条路作为某条增广轨的路又被删掉了,在循环结束时1和K都没有匹配,那这样结果应该再+1,为什么不在主程序最外面加上一个while true do,然后判断是否有解在跳出呢?可能说得有点乱,希望高人指点.
我现在已经看懂了那个find函数,但是现在我不明白为什么在主程序中调用这样的话就可以实现二分图匹配?
ans:=0;
for i:=1 to n do
if find(i)then inc(ans);
writeln(ans);
假设i=1的时候匹配了一个点K,后来1-k这条路作为某条增广轨的路又被删掉了,在循环结束时1和K都没有匹配,那这样结果应该再+1,为什么不在主程序最外面加上一个while true do,然后判断是否有解在跳出呢?可能说得有点乱,希望高人指点.
1匹配K..然后假设从M找增广路时,找到了K点,这时LInk[k]=1..那么再重新从1找增广路.如果找到L,
则1与L匹配成功,M则与K匹配
则1与L匹配成功,M则与K匹配