关于构造方案
  • 板块CF590E Birthday
  • 楼主bigtele
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/18 16:47
  • 上次更新2023/11/3 09:05:29
查看原帖
关于构造方案
771342
bigtele楼主2023/7/18 16:47

这题最后要构造一个最大独立集方案,题解里二分图大部分都是拿匈牙利写的,但是我叛逆想拿网络流写,所以只看到了 @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 里的分层数组)。

2023/7/18 16:47
加载中...