NOIP2013 解题报告
阅读原文时间:2023年07月08日阅读:1

TG Day1 T3 货车运输

考虑货车的运输路径,最小边肯定是越大越好。

那就把图的最大生成树拉出来,每一辆货车在上面都有唯一确定的运输路径,否则必然会经过一条更小或相同的边。

然后倍增求路径上的最小值即可。

TG Day2 T2 花匠

如图,绿色点代表转折点,红色点代表非转折点。

若选取了两个相邻的绿色点,则它们之间的红色点均不能选取。所以说如果方案中存在红色点,它相邻的绿色点最多只选取了一个,把该红色点换成未选取的绿色点一定不劣。

而绿色点全部选取是合法的,所以答案就是绿色点的个数。

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章