CVBB ACM Team

已知有向图，填充剩下的边使得其变成竞赛图，使其中三元环数目最大

既然是一张竞赛图，我们选出任意三个点都可能成环

总方案数为

$${n \choose 3}$$

如果三个点不成环，会发现它们的度数是确定的，入度分别为$2,1,0$，出度为$0,1,2$

所以一个点的任意两个入度，都会对答案产生一个负的贡献

所以三元环数量为

$${n \choose 3} - \sum\limits_{i = 1}^{n} {inde[i] \choose 2}$$

我们要最大化三元环数目，就要最小化$\sum\limits_{i = 1}^{n} {inde[i] \choose 2}$

考虑建模，使用费用流

每条边可以将入度分给，也仅可以分配给两端点中的一个

我们就每条边建一个点，从$S$向每条边建出来的点连一条$(1,0)$的边，表示能产生一个流量

然后该边的点向那两个端点分别连一条$(1,0)$的边，表示能产生$1$个入度

然后考虑每产生一个入度的影响

考虑到

$${x \choose 2} - {x - 1 \choose 2} = x - 1$$

所以每增加一个入度，使得入度为$x$时，会多产生$x - 1$个贡献

按照费用流的套路，我们对每个点每一种度数建一条到$T$的边(1,x - 1)，表示消耗这么多三元环

按照费用流的性质，一定会优先选择权值较小的边，也就是逐层增加

建图时，还要考虑原来已有的边

然后就做完了