关于一个貌似正确结论的不正确结果

结论:在二分图(已分成A组和B组,从B组中找A组的匹配)的查找过程中,对于一个B组中的点(已匹配),若从该点对应的A组中的点出发未找到增广路,则此后再也不会从该点出发找到增广路(即在寻找增广路的过程中遇到该点直接跳过)。
(应该是正确的吧)
但是运用后中出现了WA。。。
所以想请大佬看看是因为什么问题
下面是AC的函数代码块(注:其他地方并无错误)
inline bool bigger(int xs)
{
for (int k=1;k<=a;k++)
{
if(road[xs][k]&&!mark[k])
{
mark[k]=1;
if (d[k]==0||bigger(d[k]))
{
d[k]=xs;
return true;
}
}
}
return false;
}

下面则是有两个WA的函数代码块

inline bool bigger(int xs)
{
for (int k=1;k<=a;k++)
{
if(road[xs][k]&&!mark[k]&&!imp[k])
{
mark[k]=1;
if (d[k]==0||bigger(d[k]))
{
mark[k]=0,d[k]=xs,s[xs]=k;
return true;
}
mark[k]=0;
}
}
imp[s[xs]]=1;
return false;
}

1 条评论

  • 1

信息

ID
1212
难度
7
分类
图结构 | 二分图 点击显示
标签
(无)
递交数
2246
已通过
500
通过率
22%
被复制
4
上传者