本文出自 http://blog.csdn.net/shuangde800
题目大意
给你一个n个点m条边的无向无环图,在尽量少的节点上放灯,使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。
在灯的总数最小的前提下,被两盏灯同时被照亮的边数应该尽量大。
思路
这是LRJ《训练指南》上的例题。
这题教会了我一个很有用的技巧:有两个所求的值要优化,比如让a尽量小,b也尽量小
那么可以转化为让
M*a+b尽量小,其中M应该是一个比“a的最大值和b的最小值之差”还要大的数
最终的答案为ans/M, ans%M
回到这题,要求放的灯总数最小,被两盏灯同时照亮的边数尽量大。
因为每条边要么被一盏灯照亮,要么被两盏灯照亮,所以可以转换为:
求:放的灯总数量最少,被一盏灯照亮的边数尽量少。
就可以变成球 M*a+b 的最小值,a为放置的灯数量,b为被一盏灯照的边数
f[u][1]表示u点放灯时的整个子树最小值
f[u][0]表示u点不放灯时的整个子树最小值
如果u放,那么u个子结点可以选择放,也可以不放,选择其中较小的值。如果选的是不照,就要增加一条只有一个灯照的边
如果u不放,那么其子结点就必须选择要放,而且每条边都只有一个灯照
下面的我的代码和书上实现的不一样,更简洁
代码
<script src="https://code.csdn.net/snippets/563.js" type="text/javascript"></script>
分享到:
相关推荐
Placing const in Declarations by Dan Saks
外贸英语函电chapter-8-Placing-Orders-and-Executing-Orders.ppt
Android-Img-Placing-Game 游戏用于将图像放置在正确的背景上
Placing of blinding Layer for Foundation→ Installation of Precast Concrete Blocks→ Placing of Filter Layer Rock on the Excavated Slope→ Placing of Quarry Run as Rock Mound behind Blocks→ Placing ...
compatibility (EMC), using a single set of standards and placing a single mark on the products to allow them to be sold around the world. Unfortunately, that aspiration will not become reality any ...
3.5.6 Placing Decoupling Capacitors 3.5.7 布局前操作 3.5.8 Post-Placement Operations 3.5.9 Crossprobing 第4章 临时封装 4.1 概述 4.2 建立临时表贴封装 4.3 Creating Temporary Leaded Packages 第5章 电压...
BINARY OPTIONS SYSTEM FOR PLACING TRADES ON ANY CURRENCY PAIR
(~6% increase) and placing an order (~10% increase). Furthermore, we find interesting heterogeneous treatment effects that align with social learning mechanism: the effect of the integrated Facebook ...
If we would represent the same field placing the hint numbers described above, we would end up with: *100 2210 1*10 1110 As you may have already noticed, each square may have at most 8 adjacent ...
n queen problems- c program for placing queens in a chess board
第四节:元件摆放指南(Placing Components) 第五节:动态走线指南(Creating Traces with Interactive Routing) 第六节:高速走线指南(Creating High-speed Traces) 第七节:PADS Router 自动走线指南(Autorouting) ...
第四节:元件摆放指南(Placing Components) 第五节:动态走线指南(Creating Traces with Interactive Routing) 第六节:高速走线指南(Creating High-speed Traces) 第七节:PADS Router 自动走线指南(Autorouting) ...
The third objective is to present design methodologies for efficiently placing on-chip decoupling capacitors in nanoscale integrated circuits. Finally, the fourth objective is to suggest novel ...
This project explains an industrial process that involves picking and placing a material/product on a conveyor and a pusher pushing it to a box at a specified destination detected by a proximity ...
design, simulating the design, synthesizing the design, placing and routing the design, using VITAL simulation to verify the final result, and a new technique called At-Speed debugging that provides ...
windows forms app simple made easy with naive project to play cards or placing them
用于ADS2011功率管开发,最好是那本经典教材
本科论文对于我的本科论文,我正在尝试开发一种有效的算法来放置服务器,以便即使在k个服务器发生故障后,每个客户端也至少可以在d距离内获得ap台服务器。
The placing on the boards is slightly different around the TC3X7 itself dependent of the space (socket need more space and has through hole), but the most components are on the same location. All ...
Linqer is a software application which can be used in order ... Moreover, by placing the last mentioned files to an external data device (e.g. pen drive), you can use Linqer on any PC you can connect to.