网上找的一些综合材料专题cave

1、题目来源：CEOI 97者：情况：搜索做这道题是绰绰有余的，不过听说还可以 DP，但我不知道如何实现。同时，我觉得本题可能还有其他优秀算法。理由：图很特别，特殊的树带上一个特殊的圈。题目的各种条件和限制也显得比较的纷繁。可以作为一道优秀的搜索题，同时还是一道很不容易看出来的 DP 问题。这道题或许还有别的好算法，希望大家都能从这道题中有所启发。The CaveTime limit per test: 1s Memory limit: 1000KThere is a lot of caves in Byand. This is the map of one of them:exactly onc

2、e.An exception from this rule is the entrance chamber where every tour begins and ends, you areallowed to visit this chamber exactly twice. The tour route should be fit for aage visitor andcontain as few hard passages to walk through assible.ExleConsider the cave showedto walk through.he figure. The

3、 entrance chamber is 1. The dashed passages are hardRoute 1, 5, 4, 6, 8, 7, 2, 3 contains no hard passages at all. The final chamber, number 1, is impdand not listed.TaskWrite a programt:reads the description of a cave from the text file CAV.IN;finds a route through the cavet begins and endshe entra

4、nce chamber, lets the visitors seeall the other chambers only once and contains as few hard passages aswrites the result to the text file CAV.OUTsible;InputThere are twoegers n, k (separated by a single space)heline of the text file CAV.INTheeger n, 3 n 500, is the number of all chambers in a cave a

5、nd k is the number of all itsouter chambers, k 3. The chambers are numbered from 1 to n. Chamber 1 is the entrancechamber. Chambers 1, 2, ., k are outer chambers. They do nohis order.ve to appear on the outer circleThe next 3n / 2 lines contain descriptions of the passages. Each description consists

6、 of threeegers a, b, c separated by single spa. Theegers a and b are numbers of chambers at theends ofsage. Theeger c equals 0 or 1, where 0 meanst the passage is easy to walkthrough and 1t it is hard.OutputYour program should write a sequence of negers separated by single spato theline ofthe text f

7、ile CAV.OUT; the sequence has to begin with 1 (the entrance chamber). The followingn 1egers should be consecutive chambers on the computed route.ExleFor the text file CAV.IN:813753230017827001000525441One of the correct solutions is the text file CAV.OUT:1 5 4 6 87 2 3山洞时间限制: 1s内存限制: 1000Kand 的地方有很多

8、山洞。下面是一个山洞的地图：一个名叫 By13586724Byand 的所有山洞都有着如下特征：所有的大厅和通道都在同一水平面上。没有两条通道相交。有一些大厅位于山洞的外圈上，称其为外厅。其他所有位于外圈的大厅被称为是内厅。有且仅有一个外厅有着一个通向山洞的。每一个大厅都恰好连接着三条通道，通向三个不同的另外的大厅。对于任意一个外厅，则有两条通道通向外圈上另外两个邻接者的外厅，另一条通道连接着一个内厅。连接外厅的通道称作外通道，其他的称作内通道。保证可以在只使用内通道的情况下从任意一个大厅走到另一个大厅。如果不重复走通道，则方案唯一。规定通过每条通道的程度并不是一样的。所有通道分为两类：容易的

9、和的。现已决定将所有山洞向公众开放。为保证顺畅和安全地通过山洞，游客必须沿着预先标记好的路线游览，并且保证对于每个大厅且仅一次。唯一的例外是的大厅，你应在开始和结束的时候分别一次。路线应该适合一个一般游客，也就是说，最好是包含尽可能少的通道。样例考虑的这样一个山洞。作为的大厅是 1 。画虚线的通道是通道。路线 1, 5, 4, 6, 8, 7, 2, 3 没有包括任何通道。终点大厅 1 号已经暗含，此处不再列出。任务编写一个程序，要求：从文本文件 CAV.IN 读入一个山洞的描述；找出一条通过所有大厅一次且仅一次（除外）的路线，使得该路线的起止大厅是给定为的大厅，并且使得该路线包含的通道尽可能的少；将结果写入文本文件 CAV.OUT。输入CAV.IN 的第一行有两个由一个空格隔开的整数 n，k，3 n 500，是该山洞的大厅数，k 是该山洞的外厅数，k 3 。大厅由 1 到 n，大厅 1 即大厅。大厅 1, 2, ., k 即所有外厅。需要注意的是，外厅并不一定按照这个顺序出现在外圈上。接下来的 3n / 2 行则是通道的描述信息。每条描述信息由三个整数 a, b, c 组成，它们间由一个空格隔开。整数 a 和 b 是通道两头的大厅。整数 c 可以是 0 或者 1，其中 0 表示该通道容易通过，1 则表示该通道是一条通道。输出你的程序应该输出一个包含 n