【bzoj1027】[JSOI2007]合金

2014年12月9日3,6378

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

3 2
0.25 0.25 0.5
0 0.6 0.5
1 0 0
0.7 0.1 0.2
0.85 0.05 0.1

Sample Output

2

题解

好像是道很厉害的题

第三维可以由前两维确定,所以可以无视

两种原料能配成的产品一定在两点间线段

转化成在m个点里找最少点,围成的多边形包括了n个目标点

floyd求最小环。。。

具体就是如果目标点在线段a,b的一侧则dis[a][b]=1

否则dis[a][b]=inf

答案是min{dis[i][i]}

特判下所有点重合/共线

 

  • NanoApe2015年5月1日 下午4:39 回复

    代码中
    if(c1)return 1;
    if(c2)return 2;
    应为
    if (!c2) return 1;
    if (!c1) return 2;

    #1  
    • LoL2015年5月14日 下午12:48 回复

      错了啊 这样 return 3 没用了, 共线但不在两点之间的情况没有了

      #11
    • 傲寒2016年3月20日 下午6:57 回复

      我交了一下都A啦 QWQ

      #11
  • R-sang2016年4月16日 下午10:34 回复

    黄学长音乐能不能换一下?

    #2  
    • 2016年4月19日 上午8:47 回复

      竹取飞翔后面突然画风不对了2333

      #21
  • 徐亦轲2016年8月8日 下午6:50 回复

    黄学长您试一下这组数据会WA= =
    4 1
    0.5 0 0.5
    0.5 0.25 0.25
    0.4 0.4 0.2
    0.6 0.4 0
    0.5 0.3 0.2
    答案是3,您的输出是-1

    #3  
  • DZYO2017年11月19日 下午9:03 回复

    卡掉了啊。。
    5 1
    0.6 0.3 0.1
    0.6 0.3 0.1
    0.6 0.3 0.1
    0.6 0.3 0.1
    0.2 0.1 0.1
    0.6 0.3 0.1

    #4