这道题目是一个模型:给连通的无向图加边,使得无向图没有桥(即变成边双连通分量),最小化加边数
因为边双连通分量本来就没有桥,所以我们考虑对整个图求一遍边双连通分量(使用 tarjan 算法),然后将边双连通分量缩为一个点考虑。那么缩完点后得到的图一定是一棵树(因为图中不可能存在环)
然后要加的边的个数就是\(\lceil\frac{cnt}{2}\rceil\),其中\(cnt\)是图中度数为\(1\)的点数
先证这是下界,每一次操作顶多使度数为\(1\)的点消失两个,考虑一下最后的细节问题即可
然后构造一下:
直接考虑节点数量在\(2\)以上的情况,我们任选一个度数大于\(1\)的点(一定找得到)作为根节点,然后这棵树就长这个样子:
每个子树都有若干个叶子,数目设为\(a_1\),\(a_2\),...,\(a_n\)(假设已经从大到小排好序了)
我们每次选择不同的子树的两个叶子连边,相当于把序列{\(a\)}中选两个数\(-1\)
先假设\(\sum_{i=1}^{n-1}a_i≥a_n\)
我们每次操作都让\(a\)中最大的数和最小的数进行减一(中间注意动态调整),那么最后要么全部变为\(0\),要么还剩下一个\(1\)
对于前面一种情况,此时就已经符合题意了,对于后面一种情况,此时在让这个叶子节点与根节点进行连边即可,不难算出添加的边数是以上结论给出的式子
如果\(\sum_{i=1}^{n-1}a_i<a_n\)怎么办?
此时,我们换根,让\(a_n\)所对应的子树的顶点作为根,直到对应的序列满足\(\sum_{i=1}^{n-1}a_i≥a_n\)
证毕
这种每次按照单位数量选两个减的好像都是让最大的和最小的减,然后中途动态调整
标签:连通,子树,边双,sum,路径,节点,冗余,分量 From: https://www.cnblogs.com/dingxingdi/p/18012894