[bzoj 1027][JSOI2007]合金（解析几何+最小环）
浏览数：57 /
时间：2015年06月09日
题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1027
分析：
首先因为一个合金的和为1，所以考虑2个材料合金能否合成一个需求合金的时候，只要考虑前两个值就可以了。
我们如果把这两个值放到平面直角坐标系中，设两个材料合金坐标分别为(x,y)和(m,n)，那么易得这两个材料合金可以合成的需求合金对应的点在(x,y)(m,n)两点之间的线段上。（高中数学向量的性质可以证）
那么问题就转化为了：平面上有m个材料合金点，n个需求合金点，要求选出最少的材料合金点，使得这些点能把所有n个需求合金点全部围起来。
处理方法是：
枚举每两个材料合金点p,q，判断是否所有n个需求合金点都在有向线段pq的左侧，如果是，则g[p][q]=1，否则g[p][q]=0。这样做的好处是如果图g中存在一个环，那么就表示n个点都在这个环里面，这个环上的点（即材料合金点）就是满足的一个材料合金点的组合。既然要材料合金点最少，那么就等价于在g图中找最小环。然后问题就解决了。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
