大家来看一下这道大神的题辣!!!!

回复帖子

@captain 2016-10-10 18:25 回复

1.最小生成树 ( mst.cpp,c,pas )时限1S

【问题描述】

给定一个简单图 G=(V,E,W),V 为定点集合,E 为边的集合(无重边,即任意两个顶点之间至多只有一条边),W 为定义在 E 上的权函数(值为整数)。给出其上的一棵生成树 T,现在要求用最小的代价修改 W,使得 T 是 G 上的一棵最小生成树(一个图可以有多棵最小生成树,只要 T 的边权和最小即可)。对于任意一条边 Ee ∈ ,修改方法为:

» 增加 e 的权值,即令W’(e)=W(e)+ ∆ (e),则修改该边的代价为∆ (e)。

» 减小 e 的权值,即令W’(e)=W(e)- ∆ (e),则修改该边的代价为∆ (e)。

» 不改变 e 的权,即W’=W(e),修改代价为∆ (e)=0。

请注意:修改后的权函数 W’的值域也为整数。

总的修改代价为所有∆ (e)的和

【输入文件】

第一行为 N、M,其中 N 表示顶点的数目, M = 表示边的数目。顶点的编号为 1、2、3、……、N-1、N。接下来的 M 行,每行三个整数Ui,Vi,Wi,表示顶点 Ui 与 Vi 之间有一条边,其权值为 Wi。所有的边在输入中会且仅会出现一次。再接着 N-1 行,每行两个整数 Xi、Yi,表示顶点 Xi 与 Yi 之间的边是T 的一条边。

【输出文件】

只有一个整数 S,表示最小修改代价。

【样例输入】

6 9 1 2 2 1 3 2 2 3 3 3 4 3 1 5 1 2 6 3 4 5 4 4 6 7 5 6 6 1 3 2 3 3 4 4 5 4 6 【样例输出】

8 【样例说明】

边(4,6)的权由 7 修改为 3,代价为 4

边(1,2)的权由 2 修改为 3,代价为 1

边(1,5)的权由 1 修改为 4,代价为 3

所以总代价为 4+1+3=8

修改方案不唯一

@captain 2016-10-14 20:45 回复 举报

以下为出题人给的题解:

要使生成树为最小生成树,那么当树上一条边去掉后,树呗分成两部分,其它的能使树连通的边的权不能大于去掉边的权。

我们定义去掉树上某边,再加入其它边树仍连通,那么树边与加入边相关,将所有边看成点,相关边相连,于是树边和加入边构成一个二分图。

后于是问题转化为:二分图左边的每个点权值可以减小,右边每个点权值可以增大,要求使左边任意点不大于右边与它相关的点。

然后先将右边点全部增大使其满足要求,这构成初始状态,下面进行改进,即对左右进行减小。

左边点权值减小会使代价增加,右边权值减小代价减小,但是减小时要保证左边永远不大于右边,右边的点不小于初始值。

这样,如果右边某个点减小,所有与之相关的点都减小,否则左边与之相关点会大于它。

我们每次同时减小一些点,尽量使右边点与左边点数量差值大,这样代价减少量便大。

选择右边点时必须选择左边所有与之相关点,这就是闭合图(详见胡伯涛论文)

用网络流或二分图找出每次集体减小的点。

注意,每次必须找可减小的点中相等的且最大的点,将之减小到第二小的。

以上算法是本人乱搞的,国家队有人对此题做过详尽分析。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。