CF387D

题意分析

操作最少的次数,构成有趣图,注意无重边,有向边。

  • 操作分为加边和删边。
  • 有趣图定义
    • 有一个中心,满足此点有自环,且与其他结点有双向边。
    • 除中心点外的结点,满足出度 = 入度 = 2。

算法分析

1、仔细分析有趣图的定义,发现如下性质:

  • 中心的边数为 $(n-1)\times 2+1$,也就是它与其他结点要有双向边再加自己的一个自环,无重边所以构造中心点时不可能做删除操作,只能加边或不操作。
  • 其他结点的出入度为 2,排除掉与中心点连接的双向边,其点的度一定为一进一出。

2、如何判断结点的度满足一进一出。

图一,图二都是满足结点度一进一出。所以 $n$ 个结点需要 $n$ 条相连边(首尾)。

图三不满足,只有两条相连边 $(e_1,e_2)$ 或者选择 $(e_1,e_3)$ 即有用边,还需要添加 $n-2$ 边有用边,同时还要减掉 1 条边,即总边数减去有用边,也就是要删除的无用边。

方法1:拆点,一个点拆为进点和出点,建立二分图。

左边的点求匹配,最大匹配就是有用的边。

方法2:直接将图看成二分图,利用有向边每个点都求匹配。

3、枚举每个点做中心点。

  • 中心点 V,计算维护中心需要的边 $(n-1)\times 2+1-\sum{V发出的边}$

  • 删除 V 点,也就是包含相应的边

  • 剩下的图,计算最大匹配,满足一进一出的边数需要的操作(添加边 + 删除边)。