信息学小生成树.pdfVIP

试题简述

•给定一个无向带权连通图G

–权值均为正整数

•可以通过两种操作:

–将一条边的权值减少1,费用为a

–将一条边的权值增加1,费用为b

•求最小代价的操作使得:

–图的最小生成树唯一

数据分布

测试点特点

19

n≤7，m≤10,a=10,b=1

9

2n≤50,000，m≤1,000,000,a=10,b=1

9

3n≤100，m≤1,000,a=1,b=10

9

4~5n≤500,000，m≤1,000,000,a=1,b=10

6~10输入数据给定☺

得分情况

讨论☺

最小生成树唯一

•如何判断最小生成树唯一

–求次小生成树,看是否一样大☺

•“最小生成树唯一”的性质

–考虑Kruskal算法,按边权为阶段从小到大考虑

–当考虑权值为x的边（可能有多条)

•EA:有一部分是没有用的(连接已经的连通块)

•EB:另外一部分是有用的(选择一部分作为mst中的边)

•如果EB中有环→添加方式有多种

•如果EB中无环→添加方式唯一→最小生成树唯一

问题分析

•设原图为G,边权修改后的图为G*

•定理1:目标树存在

–原图中存在一棵生成树T,在G*中是唯一的最小生成

树

•定理2:目标树内的边只减权,树外只

•定理3:仅加1,减权仅减1

问题分析

•定理4:按照边权作为阶段,每个阶段加边,G

和G*的连通性一致

•定理5:目标树一定为G的某一棵最小生成树

•猜想6:G中任意一棵MST均可作为目标树

若猜想6成立

•算法:

–任意求一棵生成树,目标将其改进为唯一的最小生成树

–最小权闭合子图问题

•最小割解决x

x

x

–优化:

•1.对于不同边权X,每一个边权