【WC2007】石头剪刀布

作者：盐析白兔 | 2024-02-06 21:27:31

踩

wc2007

题面

先放链接：https://www.luogu.org/problemnew/show/P4249
简述题意：一个n个点的竞赛图，给定其中一些边的方向，确定剩余边的方向使得图中的三元环数量尽量多

分析

这个题想了好久啊qwq，想的全是错的建图…最后还是看题解了才搞明白
我们发现构成三元环这个条件比较难以考虑，所以考虑反过来：什么情况下会无法构成三元环。任意三个点无法构成三元环，一定是其中一个点出去两个边，一个点进去两个边，一个点一进一出。那么考虑入度，当一个点有一个入度的时候，没有问题；当一个点有两个入度的时候，会有一个三点组无法构成三元环；进而当一个点有 $k$ 个入度的时候，会有 $C\binom{2}{k}$ 个三点组无法构成三元环。每增加一个入度，会使得之前的每个入度都可以与他组成一个使这个点有两个入度的三点组，即减少之前的入度个数的三元环。注意算了入度就不要再算出度了，因为边 $(u,v)$ 会是 $u$ 的出度，也会是 $v$ 的入度，不要重复计算。
如此我们的思路就比较清晰了，对于一条边 $(u,v)$ ，一定会使得

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/64628