首页 > 搜索 > BFS搜索 > HDU 1689 Alien’s Necklace-BFS-[解题报告] C++
2013
12-21

HDU 1689 Alien’s Necklace-BFS-[解题报告] C++

Alien’s Necklace

问题描述 :

JYY is taking a trip to Mars. To get accepted by the Martians, he decided to make a magic necklace for their king. (Otherwise, JYY will be eaten) Now, he has collected many magic balls, and he is going to string them up.
Unfortunately, only particular pairs of balls can be adjacent in the necklace, otherwise they will explode. Notice that the first and the last ball in the necklace are also adjacent. Besides, the Martians think even numbers are unlucky, so the number of balls in the necklace must be odd. (Of course each ball can be used only once)
A necklace contains at least 3 balls. Because the balls are really precious, JYY wants the necklace has as few balls as possible. (Then he can give rest balls to his GF)
So JYY wonders the number of balls he has to use to make this necklace.

输入:

The input consists of several test cases. There is a single number above all, the number of cases. There are no more than 20 cases.
For each input, the first line contains 2 numbers N and M, N is the number of balls JYY collected, and M is the pairs of compatible balls. Balls are numbered from 1 to N. Followed M lines, each contains 2 numbers A and B, means that ball A and ball B are compatible. For each case, 0 < N <= 1,000, 0 < M <= 20,000.

输出:

If the gift can’t be done, just print "Poor JYY." in a line, otherwise, print the minimal number of balls in the necklace. Use the format in the example.

样例输入:

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

样例输出:

Case 1: JYY has to use 3 balls.
Case 2: Poor JYY.

题目意思是检测最小奇数环 并输出结果

 

对于该类题目 分析了下复杂度 可以对各个点进行一一枚举 对于每次的枚举 记录访问到该点时的深度 当下一次访问时只要将当前深度加上访问到该点的深度就能计算出总共所用去的点数 使用2个队列  以形成逐层遍历(保证了路径的不重复) 感觉很不错 每次枚举计算出的最小值可以作为下一次的阀值 从而达到了缩小规模的目的

 

OK 下面是代码啦….

 

 

 

 

 

解题报告转自:http://www.cnblogs.com/zhuangli/articles/1285516.html