# CF387D

# 题意分析

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

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

# 算法分析

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

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

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

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

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

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

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

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

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

  • 中心点 V,计算维护中心需要的边 (n1)×2+1(n-1)\times 2+1-\sum

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

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

更新于