首页 > Web开发 > 详细

bzoj 1027[JSOI2007]合金 - floyd + 凸包

时间:2018-02-14 13:46:47      阅读:231      评论:0      收藏:0      [点我收藏+]

1027: [JSOI2007]合金

Time Limit: 4 Sec  Memory Limit: 162 MB

Description

  某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的
原材料中铁铝锡的比重不同。然后,将每种原材料取出一定量,经过融解、混合,得到新的合金。新的合金的铁铝
锡比重为用户所需要的比重。 现在,用户给出了n种他们需要的合金,以及每种合金中铁铝锡的比重。公司希望能
够订购最少种类的原材料,并且使用这些原材料可以加工出用户需要的所有种类的合金。

Input

  第一行两个整数m和n(m, n ≤ 500),分别表示原材料种数和用户需要的合金种数。第2到m + 1行,每行三
个实数a, b, c(a, b, c ≥ 0 且 a + b + c = 1),分别表示铁铝锡在一种原材料中所占的比重。第m + 2到m +
 n + 1行,每行三个实数a, b, c(a, b, c ≥ 0 且 a + b + c = 1),分别表示铁铝锡在一种用户需要的合金中
所占的比重。

Output

  一个整数,表示最少需要的原材料种数。若无解,则输出–1。

Sample Input

10 10
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0

Sample Output

5
 
 
我是个蒟蒻, 太神了
这道题可以转化成一个几何模型
对于任意两点,如果我们把他们前两种材料的的比重分别作为 x轴和y轴的坐标,那么他们能合成的比重就是线段上对应点的x, y
那么如果是多个点,能合成的范围就是这个凸包的内部(可以脑补一下)
所以如果所有需要的材料的点都在两点构成的线段的左边,我们就可以在这两点连一条1的边
这样最短路跑出的凸包一定能包围所有点
几个特判:
1、所有点都是相同的
2、所有点都在一条线段上。
 
 
 

bzoj 1027[JSOI2007]合金 - floyd + 凸包

原文:https://www.cnblogs.com/wuenze/p/8448229.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!