upd: 单向连边 \(a \rightarrow b\) ,显然应该在每一轮搜索中标记 \(b\) 集合的点。我误标记了 \(a\) ,这样就没有任何 \(a\) 类节点可以更改匹配了,完蛋。
bool hungary(int p, int id)
{
for (int i = Fs[p]; i; i = Nx[i]) {
int t = Vs[i];
if (Mk[t] == id)
continue;
Mk[t] = id;
if (!Lnk[t] || hungary(Lnk[t], id)) {
Lnk[t] = p;
return 1;
}
}
return 0;
}
int main()
{
ans = 0;
for (i = 1; i <= n; ++i)
ans += hungary(i);
printf("%d\n", ans);
return 0;
}