Codeforces 671D Roads in Yusland

题目链接

题意:给出一棵以1为根的有n个点的树与m条权值为ci的链,满足在链的两个端点的lca是他们中的一个(即这些链都是竖直的),所有节点至少被一条链覆盖,问最少选出权值和为多少的链满足方案,无解则输出-1。

 

题解:网上的做法大多是按照dfn把链离线之后用线段树维护,比较难写(大概)。然而我在某课件中看到了一种新颖的做法:应用对偶原理,将原问题转化为一个简单(?)的贪心问题,然后就要调很久了简单了很多。

 

先说对偶原理:对于一个线性规划问题,把它写成标准形式之后,大概是一个系数矩阵与未知数向量的积满足一个约束,最大化(或最小化)一个与未知数向量有关的线性表达式。然后对偶原理大概就是把系数矩阵转置,对于每一个约束建立一个变量。可能有点说不清,大概是比较抽象的缘故吧QAQ。(自行Google对偶原理其实也挺好的)

再看这道题,很快地便可以想到一个线性规划的形式,然后对偶一下:

(哇好丑啊)

然后就变成了问给每一条边赋权值,每条链上边权值之和不得大于ci,问总权值的最大值。

然后就用set的启发式合并就好了

代码: https://pastebin.ubuntu.com/p/cmjQ5x4Dv4/

写得很丑,表介意qwq

发表评论

电子邮件地址不会被公开。 必填项已用*标注