这题最后要构造一个最大独立集方案,题解里二分图大部分都是拿匈牙利写的,但是我叛逆想拿网络流写,所以只看到了 @ecnerwaIa 的题解可以参考,然而在输出方案时却出现了问题。
我想的是从源点向与源点相连的点遍历,如果流量为 1 证明没有匹配,就可以认为是一个独立的点,但是这样做交到 CF 上是错的。(我认为错的原因是这样求出来的方案中会有某个点被另一个点匹配,但是方案中也有点与这个点有关系,只是因为这个点已经被匹配了所以没有增广路)
然后 @ecnerwaIa 的题解里是这么写的:
for(int i=1;i<=n;++i){
if(dep[i]<inf&&dep[i+n]>inf){
printf("%d ",i);
}
}
但是我不能明白这样为什么是对的,求解答(dep[] 就是 Dinic 的 BFS 里的分层数组)。