关于这题答案的下界证明
查看原帖
关于这题答案的下界证明
70132
AsunderSquall楼主2021/8/24 08:56

RT,现有两篇题解感觉都在口胡,完全看不懂。

去看了 CF 官方题解,完全不知道它的 Processing an edge (u,v)(u,v) 说的是原图的边还是构造的新图的边。如果是原图的边那就和 kk 没关系了,如果是新图的边又不知道是怎么把新图的 DAG 转化成原图的 DAG 的。

或者,有人能帮忙证明下面这个东西吗?

22 个有向图 GGGG',保证 GG 中的一条边 uvu\to vGG' 中满足 u 可以到达 v。可不可以证明 GG 中的最大点导出 DAG 比 GG' 中的最大点导出 DAG 大或者相等?

2021/8/24 08:56
加载中...