Blog

BZOJ2395 Timeismoney(最小乘积生成树)

huangkui 2018年3月17日 No Comments Problem , ,

题目链接:BZOJ(权限题) 、YALIOJ Description 有n个城市(编号从0..n-1),m条公路(双向的),从中选择n-1条边,使得任意的两个城市能够连通,一条边需要的c的费用和t的时间,定义一个方案的权值v=n-1条边的费用和 * n-1条边的时间和,你的任务是求一个方案使得v最小

Hdu4966 GGS-DDU (最小树形图/朱刘算法)

huangkui 2018年3月17日 No Comments Problem , ,

题目链接:传送门 Description 有一个人,想学习N个科目,每个科目都有相应的层次 有M个课程,M个课程的要求是,你的第c个科目的层次要达到l1,才可以参加,参加完这个课程后,你需要缴费money,但你的第d个科目的层次会达到l2 问如何花最少的钱,使得每个科目的层次都达到最高

Codeforces 733F Drivers Dissatisfaction(最小生成树+LCA)

huangkui 2018年3月16日 No Comments Problem , , ,

题目链接:传送门 Description 给一张n个点m条边的连通图,每条边(ai,bi)有一个权值wi和费用ci,表示这条边每降低1的权值需要ci的花费。现在一共有S费用可以用来降低某些边的权值(可以降到负数),求图中的一棵权值和最小的生成树并输出方案。

Page 2 of 13