[bzoj 1027][JSOI2007]合金（解析几何+最小环）
2024-10-18 18:20:30
题目：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图中找最小环。然后问题就解决了。
最新文章
- CRL快速开发框架系列教程八(使用CRL.Package)
- 【转载】VC维的来龙去脉
- DataTable 分页
- ubuntu下eclipse突然崩溃，解决办法
- hdu 1690 The Balance_母函数
- 利用sql里的xpath生成表格
- 获取Storyboard中的视图控制器
- Docker - 导出导入容器
- 移动端JS判断手势方向
- HDU6166-Senior Pan-Dijkstra迪杰斯特拉算法(添加超源点,超汇点)+二进制划分集合-2017多校Team09
- 修改Java程序的进程名
- mysql 1194 – Table ‘tbl_video_info’ is marked as crashed and should be repaired 解决方法
- Centos7 Lnmp的环境搭建
- Let me introduce myself
- Dockerfile指令学习 (转)
- svn:重命名文件之后,不允许提交
- 2、图文讲解.NET CLR是什么
- eclipse中java项目转成Web项目
- blender, merge顶点
- Java多线程编程实战指南（核心篇）读书笔记（三）