首页 > 搜索 > DFS搜索 > HDU 3414-Tour Route-连通性问题-[解题报告]HOJ
2014
03-23

HDU 3414-Tour Route-连通性问题-[解题报告]HOJ

Tour Route

问题描述 :

The city is so crowded that the mayor can’t bear any longer. He issued an order to change all the roads into one-way street. The news is terrible for Jack, who is the director of a tourism company, because he has to change the travel route. All tourists want to set out from one scenic spot, then go to every scenic spots once and only once and finally return to the starting spot. They don’t care about which spot to start from, but they won’t go back to the starting spot before they have visited all other spots. Fortunately, the roads in the city have been perfectly built and any two scenic spots have been connected by ONE road directly. Jack gives the map of the city to you, and your task is to arrange a new travel route around the city which can satisfy the tourists.

输入:

Input consists of multiple test cases and ends with a line of “0”.
For each test case:
The first line contains a single integer n (0<n<=1000), representing the number of city scenic spots. Scenic spots are numbered form 1 to n.
Then n lines follows, and each line consists of n integers. These n lines make a matrix. If the element in the ith row and the jth column is 1(i≠j), it means that the direction of the road between spot i and spot j is from spot i to spot j. If that element is 0, it means that the road’s direction is from spot j to spot i. The numbers in the main diagonal of the matrix are all 0. (i and j start from 1)

输出:

Input consists of multiple test cases and ends with a line of “0”.
For each test case:
The first line contains a single integer n (0<n<=1000), representing the number of city scenic spots. Scenic spots are numbered form 1 to n.
Then n lines follows, and each line consists of n integers. These n lines make a matrix. If the element in the ith row and the jth column is 1(i≠j), it means that the direction of the road between spot i and spot j is from spot i to spot j. If that element is 0, it means that the road’s direction is from spot j to spot i. The numbers in the main diagonal of the matrix are all 0. (i and j start from 1)

样例输入:

5
0 0 1 1 1 
1 0 1 1 0 
0 0 0 1 0 
0 0 0 0 1 
0 1 1 0 0
2
0 1
0 0
0

样例输出:

1 3 4 5 2
-1


Tour Route
Time Limit:
20000/10000 MS
(Java/Others)    Memory
Limit: 32768/32768 K (Java/Others)
Total Submission(s):
466    Accepted
Submission(s): 80
Special Judge
Problem Description
The city is so crowded that the mayor can’t bear any longer.
He issued an order to change all the roads into one-way street. The
news is terrible for Jack, who is the director of a tourism
company, because he has to change the travel route. All tourists
want to set out from one scenic spot, then go to every scenic spots
once and only once and finally return to the starting spot. They
don’t care about which spot to start from, but they won’t go back
to the starting spot before they have visited all other spots.
Fortunately, the roads in the city have been perfectly built and
any two scenic spots have been connected by ONE road directly. Jack
gives the map of the city to you, and your task is to arrange a new
travel route around the city which can satisfy the tourists.
Input
Input consists of multiple test cases and ends with a line of
“0”.
For each test case:
The first line contains a single integer n (0
Then n lines follows, and each line consists of n integers. These n
lines make a matrix. If the element in the ith row and the jth
column is 1(i≠j), it means that the direction of the road between
spot i and spot j is from spot i to spot j. If that element is 0,
it means that the road’s direction is from spot j to spot i. The
numbers in the main diagonal of the matrix are all 0. (i and j
start from 1)
Output
For each test case, print all the spots No. according to the
traveling order of the route in one line. If multiple routes exist,
just print one of them. If no such route exists, print a “-1”
instead. Because the starting spot is the same as the ending spot,
so you don’t need to print the ending spot.
This problem needs special judge.
Sample Input
5
0 0 1 1
1
1 0 1 1
0
0 0 0 1
0
0 0 0 0
1
0 1 1 0
0
2
0 1
0 0
0
Sample Output
1 3 4 5
2
-1
======================================================================================
这道题到现在我心里还是虚的,poj3780明明是同一道题,相同的代码却wa了,让我怀疑自己是占特判数据的便宜水过的。
这道题首先想到的方法是暴力深搜,不出所料的tle了。
后来做了优化,竞赛图当且仅当强连通时是汉密尔顿图,于是我用Tarjan先把不是汉密尔顿图的去掉。
Tarjan是线性效率所以我并不担心。
然后我把入度为1的点跟它唯一的前驱缩成一个点,把出度为1的点跟它的唯一后继缩成一个点,还是深搜。
依然超时,看来深搜是怎么都不行了。
后来我看到了这个:http://blog.sina.com.cn/s/blog_8d84b9240101fdwj.html
于是有了下面的代码。
======================================================================================
#include<cstdio>
const int N = 1000;
bool g[N][N];
int n , next[N];
bool expand( int s )
{
    for( int i = 0 ; i
< n ; next[i++] = -1 );
    int front = s , back =
front;
    for( int i = 0 ; i
< n ; i++ )
    {
  if( i == s )  
 continue;
  if( g[i][front] )   next[i] =
front , front = i;
  else
  {
      int a =
front , b = next[front];
      while( b
!= -1 && g[b][i] )
    a = b , b = next[b];
      next[a] =
i;
      next[i] =
b;
      if( b ==
-1 )   back = i;
  }
    }
    if( g[back][front]
)
    {
  next[back] = front;
  return true;
    }
    return false;
}
bool solve()
{
    for( int i = 0 ; i
< n ; i++ )
  if( expand(i) )  return
true;
    return false;
}
int main()
{
    while(
scanf(“%d”,&n) , n )
    {
  for( int i = 0 ; i < n ; i++
)
      for( int j
= 0 ; j < n ; j++ )
scanf(“%d”,&g[i][j]);
  if( n == 1 )   puts(“1″);
  else if( n == 2 || !solve() )  
 puts(“-1″);
  else
      for( int i
= 0 , j = 0 ; i < n ; i++ , j = next[j] )
printf(“%d%c”,j+1,i==n-1?’\n’:’ ‘);
    }
    return 0;
}
参考:http://blog.sina.com.cn/s/blog_8d84b9240101fdwh.html


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  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.