- Way Selection
- 2021-11-18 21:00:42 @
结论:在二分图(已分成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 条评论
-
主子six (房佳坤) LV 7 @ 2021-11-19 20:11:28
不可以老老实实地敲匈牙利吗😅
- 1