某岛

… : "…アッカリ~ン . .. . " .. .
September 18, 2014

最小度限制生成树

http://codeforces.com/gym/100227/submission/4751186
http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html

约定结点 1 为度限制的结点。。度限制为至多 K。

先不考虑这个结点,求生成森林。(Kruskal 的话还是一趟。)。之后从 1 开始向每个森林连边(dfs1)
。则第一阶段结束后 1 。我们得到了一个度限制为 K0 的最小生成树。。(初始生成森林的连通块个数)
要想进一步得到度限制为 K 的最小生成树,还需要进行 K – K0 次 “差额最小添删操作” …

… 其实就是贪心替换、、。。设 w1[u] 为 u 结点连到根结点的边的权值(可能输入的时候有重边。。保留最小的。)
。 从根结点 dfs2 下去。。得到每个结点到根结点路径删最大的边的权值和编号。mx[u], si[u]。
。。则选择 u 结点进行替换的话。。产生的收益就是 mx[u] – w1[u] 。。。枚举每个结点。。找出收益最大的。
。。迭代 K – K0 次即可。。(若某轮收益已经为 0。。则可直接 break 掉。。)

————————————————————————
实现过程中需要一个边表用来跑 Kruskal 。。
一个支持 del 操作的手写邻接表、。。。

    inline void del(int i){
        if (!prd[i]) prd[hd[aa] = suc[i]] = 0;
        else suc[prd[suc[i]] = prd[i]] = suc[i];
    }

    inline void dell(int i){
        del(i), del(i^1);
    }

    inline void add(int x, int y, int w){
        ww[m>>1] = w, prd[hd[x]] = m, suc[m] = hd[x], hd[x] = m, to[m++] = y;
        swap(x, y), prd[hd[x]] = m, suc[m] = hd[x], hd[x] = m, to[m++] = y;
    }

//if (!prd[i]) prd[hd[aa] = suc[i]] = 0;
(这个判断之前都是写的是 hd[aa] == i 。。。如果写成 !prd[i] 的话。。则这一部必须把 prd [] = 0 也得维护掉。。。。
(。。用前者的话不维护也行。。总之敲的时候不多加小心的话是不行的呢、。)