FJoi2017 1月20日模拟赛 直线斯坦纳树(暴力+最小生成树+骗分+人工构造+随机乱搞)
【题目描述】
给定二维平面上n个整点，求该图的一个直线斯坦纳树，使得树的边长度总和尽量小。
直线斯坦纳树：使所有给定的点连通的树，所有边必须平行于坐标轴，允许在给定点外增加额外的中间节点。
如下图所示为两种直线斯坦纳树的生成方案，蓝色点为给定的点，红色点为中间节点。
【输入格式】
第一行一个整数n，表示点数。
以下n行，每行两个整数表示点的x,y坐标。
【输出格式】
第一行一个整数m，表示中间节点的个数。
必须满足m
<= 10 * n
以下m行，每行2个整数表示中间节点的坐标。
以下n+m-1行，每行2个整数u,v表示编号为u和v的两个节点之间有边直接相连，边的权值为两点的曼哈顿距离，即|x[u]
– x[v]| + |y[u] – y[v]|
输入数据给定的点的编号为1..n，选手输出的中间节点的编号为n+1..n+m
【样例输入】
4
-1
0
0
-1
1
0
0
1
【样例输出】
1
0
0
1
5
2
5
3
5
4
5
【格式说明】
选手可使用test.exe对数据进行测试
在命令行下使用“test
x”即可测试rsmtx.in和rsmtx.out
（注：x必须是一个字符，即“test
1234”等价于“test
1”）
使用“test
@”即可测试样例
测试结束前1小时发布gen.exe，选手将该程序与所有输入输出文件（rsmt0..9
.in /
.out）放在同一目录，运行后生成rsmt-upload.cpp，测试结束时上交rsmt-upload.cpp而非rsmt0..9.out
若选手没有完成某个测试点，可不必生成该测试点的输出文件，gen.exe会自动跳过该测试点。
【得分说明】
若选手的解合法，则该数据点至少得1分
设选手的答案为ans，标程的答案为std。
若ans
>= std，则选手得分为10
* (std/ans)^w，其中w是该测试点的得分系数。
若ans
< std，则所有选手中的最优解作为std，该选手得12分，其他选手的得分为12
* (std/ans)^w
Solution
第一次做提交答案型的题目耶
在线下，我们暴力将所有点O(n*n)枚举，把可能的中间点全数添加（中间点即任意两点的坐标拉成相同的，连个边），跑个prim最小生成树算法就行了。听说直接跑可以ac。我比较弱，人工手模两个点拿20分而已。
标解：前四个数据点,有 n <= 8,使用人工构造、随机化搜索算法、状态压缩动态
规划等均可求出最优解。
第 5 个至第 8 个数据点,所有的点排布在两行上,即点的 y 坐标只有 2 种取
值。故我们可以根据 x 坐标的顺序从左至右进行状态压缩 DP,状态为当前列上
的两个点的连通情况和是否有需要加入斯坦纳树的点,共四种情况:两个点属于
一个连通块;两个点不属于同一个连通块,此时有 3 种情况:两个块内都存在需
要加入斯坦纳树的点,其中某个块存在需要加入斯坦纳树的点(因为有 2 个连通
块,故这种情况有 2 种)。依据这种状态设计进行状压 DP 即可,值得注意的是本
题需要输出方案,故还需保存 DP 过程中的转移路径,并编写程序输出。
最后 2 个数据点为纯随机数据点,适合模拟退火等随机化搜索算法,或一些贪心+构造的策略,是开放性的问题,也可以参考《FLUTE: Fast Lookup Table
Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design》等文
献提供的方法。
最新文章
- js toString()
- UrlEncoder url编码
- 转：客制FORM调用会计科目弹性域/根据科目取得CODE_COMBINATION_ID
- JAVA单向/双向链表的实现
- Oracle删除指定用户下所有对象
- linux下用top命令查看cpu利用率超过100%
- 硬件相关-JTAG接口
- Java多线程之synchronized（三）
- js date相关学习!
- python——模块和包 需要注意的地方
- ES6中export及export default的区别
- MVC，MVP和MVVM三种开发模式
- tomcat简介与配置
- 【NLP】MT中BLEU评分机制
- （转）Linux tcpdump命令详解
- 关于haproxy多域名证书的配置
- centos7设置SSH安全策略–指定IP登陆
- P1099 树网的核 && P2491 [SDOI2011]消防
- system.data.oracleclient 需要 8.17 需要oracle客户端问题
- [Cocos2d-x for WP8学习笔记] 获取系统字体