| 题目名称 | 1561. [WC 1999]迷宫改造 |
|---|---|
| 输入输出 | rebuildmaze.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 10000 ms (10 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-03-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：4， 通过率：25% | ||||
 cstdio |
100 | 0.018 s | 0.98 MiB | C++ |
 frontier |
90 | 0.021 s | 1.15 MiB | C++ |
|
frontier |
90 | 0.023 s | 1.28 MiB | C++ |
|
frontier |
50 | 0.018 s | 1.28 MiB | C++ |
| 关于 迷宫改造 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @cstdio :
第4个点我算出来是11哎，手画了一下好像11可以 | ||||
|
回复 @cstdio :
我是蒟蒻，怎么可能觉得水，我是觉得斯坦纳树太神了不会做，发现可以卡常数过去（明显就是乱搞） 不乱搞题是因为最近好像得了手残+脑残光环，交题10次（10次是少的）内定不过，现在攒题攒了好几道   Chenyao2333
2014-03-30 11:05
4楼
| ||||
|
回复 @Chenyao :
啊……神犇为何这么热衷于发布题解……是因为嫌题太水懒得秒了吗…… | ||||
|
floyd求出任意两点间最短路,最优解的情况一定是两个人到一个点汇合,之后从这个点到另一个点于第三个人汇合,之后到达终点.或者三个人直接到一个点汇合,到达终点....计算下应该可以卡过去(斯坦纳树能吃么?)
Chenyao2333
2014-03-29 16:40
2楼
| ||||
|
这个题目我在BZOJ上过了，并且用过的代码生成了数据
不过可能有一些问题，用这篇题解http://ydcydcy1.blog.163.com/blog/static/216089040201401692156297/中的代码测试，发现有两个点WA，我自己手画了一个点发现是它错了，我造的数据没错，不知道另一个是什么情况 如果有问题联系我，换数据什么的 另外，这题实在是太TM不优美了 | ||||
输入文件中的第一行为两个整数N，M（3<=N，M<=20）。
第二行中为一个整数k，表示原迷宫中门的总个数。
第i+2（1<=i<=k）行中为四个整数Xi1，Yi1，Xi2，Yi2，表示第Xi1行第Yi1列的单元与第Xi2行Yi2列的单元之间有一扇门，其中：|Xi1-Yi1|+|Xi2-Yi2|=1。
第k+3行中为一个整数，表示p的值。
第k+3+j（1<=j<=p）行中为四个整数Xj1，Yj1，Xj2，Yj2，分别表示第j个家庭成员出发的起点位置（Xj1，Yj1）和要到达的终点位置（Xj2，Yj2），其中：Xj1<=Xj2，Yj1<=Yj2，（Xj1，Yj1）<>（Xj2，Yj2）。
注意：输入数据中同一行各相邻整数之间用一空格分隔。
为一个整数，表示你所设计的最佳迷宫中新置的门的个数。
4 4 5 1 1 1 2 2 1 3 1 2 2 3 2 4 2 4 3 1 4 2 4 3 2 1 4 3 1 2 4 2 3 1 4 4
4
WC 1999