OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HAOI2010】软件安装

【题目描述】

现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。

但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系:软件i依赖软件Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这时只...

【NOI2007】社交网络

【题目描述】

在社交网络(social network)的研究中,我们常常使用图论概念去解释一些 社会现象。 不妨看这样的一个问题。在一个社交圈子里有 n 个人,人与人之间有不同程 度的关系。我们将这个关系网络对应到一个 n 个结点的无向图上,两个不同的人 若互相认识,则在他们对应的结点之间连接一条无向边,并附上一个正数权值 c, c 越小,表示两个人之间的关系越密切。 我们可以用对应结点之间的最短路长度来衡量两个人 s 和 t 之间的关系密切 程度,注意到最短路径上的其他结点为 s 和 t 的联系提供了某种便利,即这些结 ...

© OI技术宅 | Powered by LOFTER