题目要求一个最小值加上一个最大值的最小值,不好直接做,考虑转化。
发现树是二分图,而由柯尼希定理可知二分图的最大匹配等于其最小点覆盖。这样就把求 \(\min(\min_{\text{生成树}}+\max_{匹配})\) 转化为了 \(\min(\min_{生成树}+\min_{覆盖})\)。
直接 \(\mathcal O(2^n)\) 枚举最小点覆盖中的点,每次做一遍最小生成树即可。时间复杂度 \(\mathcal O(2^nn^2)\)。
标签:CF1948G,min,题解,MST,mathcal,Matching From: https://www.cnblogs.com/zifanoi/p/18090513