laekov naiiiiiiiiive
问题
一个无向图 (G), 每条边 (e) 有两个边权 (a_e, b_e).
求一个生成树 (T) 使得 ( (\sum_{e \in T} a_e) * ( \sum_{e \in T} b_e) ) 最小.
多项式算法就是胜利w.
原题
搜 bzoj2395.
这网站里搜可以找到代码.
一个未成形的算法
正确性和时间复杂度都待证 qwq.
感觉是对的. 但是严格证明 qaq. 已经脱离理论计算机科学界太久了.
假设我们有一个生成树的序列 ( Q ) 和一个生成树池 ( P ).
算法如下
- 对 ( a ) 这一个权值跑出一个最小生成树 ( T_0 ).
- 把 ( T_0 ) 作为 ( Q ) 里的第一个元素.
- 取出 ( Q ) 里的最后一棵生成树 ( T ).
- 枚举未在 ( T ) 里的每条边, 用这条边替换掉 ( T ) 里的若干条边, 都可以形成新的生成树. 把它们全部扔进 ( P ) 里.
- 挑选 ( P ) 里 ( \sum_{e \in T’} a_e > \sum_{e \in T} a_e ) 且 ( \sum_{e \in T’} b_e < \sum_{e \in T} b_e ) 的 ( \sum_{e \in T’} a_e ) 最小的 ( T’ ), 把它加到 ( Q ) 的末尾.
- 重复 3 到 5 直到找到关于 ( \sum b ) 的最小生成树.
- 把 ( Q ) 枚举一遍就能找到答案.
对于正确性
会枚举整个 ( A ) 单增 ( B ) 单减的点列.
对于时间复杂度
每条边被踢出去后不会再被加进来, 即使被加进来也可以由不重复加边的替换方案生成.
所以 ( Q ) 的总大小有保障, 进而 ( P ) 的总大小有保障.
Historical Comments
SherlynW at 2017-10-06T19:26:31
及时的题解