首页 > ACM题库 > HDU-杭电 > hdu 2968 Museum待解决[解题报告]C++
2014
02-24

hdu 2968 Museum待解决[解题报告]C++

Museum

问题描述 :

There is this big museum, full of fancy rooms and shiny corridors. It is so large that planning any tour in it becomes a serious issue. This is where your help is necessary. You are to help in planning signs that will make navigation through the whole building much easier. The idea is that if a room has d doors leading through corridors to other rooms, these doors and corresponding corridors are (locally) labeled with numbers 1, 2, … , d. Then all visitors are advised to follow a simple procedure.

If they are in room v at the very beginning of their tour, they should choose door labelled with 1 and pass through the corresponding corridor If they are in room v and they entered it through door labelled with i, they should pick the door labelled with the next number (i.e. i + 1 if i < d and 1 if i = d) and pass through corresponding corridor. Here is a simple example, in which tourists start in room 1 and visit rooms 1, 2,3, 4,5, 6 in this order passing through each corridor at least once:

Exhibits in this museum are not only in rooms but also in corridors connecting different rooms. After all, the corridors are well suited for displaying paintings and photography! Thus we want to ensure that the tourists that follow the rules will pass through each corridor at least once, assuming they do not get bored easily and walk long enough, irrespectively of the room they started the tour in. Your task is to find such a labelling.

It turns out that there are at most 3 corridors outgoing from each room and the whole museum is connected, i.e. it is possible to walk between any two rooms, possibly passing through other rooms along the way. All corridors outgoing from a single room lead to different rooms.

输入:

The input contains several test cases. The first line contains the number of test cases t (t <= 100). Each test begins with a line containing the number of rooms n (3 <= n <= 10^5). The next n lines contain description of all corridors. i-th of them described corridors connecting the i-th room with others. It begins with an integer d (1 <= d <= 3), the number of doors in this room. d integers r1; r2; : : : ; rd follow, giving numbers of rooms that those doors lead to (1 <= rj <= n and rj != rk if j != k and rj != i).

All corridors are bidirectional, so if there is door from room x to room y, there is door from room y to room x as well. Total size of the input will not exceed 50MB.

输出:

The input contains several test cases. The first line contains the number of test cases t (t <= 100). Each test begins with a line containing the number of rooms n (3 <= n <= 10^5). The next n lines contain description of all corridors. i-th of them described corridors connecting the i-th room with others. It begins with an integer d (1 <= d <= 3), the number of doors in this room. d integers r1; r2; : : : ; rd follow, giving numbers of rooms that those doors lead to (1 <= rj <= n and rj != rk if j != k and rj != i).

All corridors are bidirectional, so if there is door from room x to room y, there is door from room y to room x as well. Total size of the input will not exceed 50MB.

样例输入:

2
6
3 4 2 3
3 5 1 3
3 6 1 2
1 1
1 2
1 3
4
2 2 4
2 1 3
2 2 4
2 1 3

样例输出:

3 4 2 3
3 5 3 1
3 6 1 2
1 1
1 2
1 3
2 2 4
2 1 3
2 2 4
2 1 3


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  3. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮