首页 > ACM题库 > HDU-杭电 > hdu 2982 Help Little Laura待解决[解题报告]C++
2014
02-24

hdu 2982 Help Little Laura待解决[解题报告]C++

Help Little Laura

问题描述 :

Laura Luo has just invented a game. Given a beautiful pencil sketch with n points, you’re to colorize it with water pens by painting circuits. Each time you paint a new circuit, starts with one point, follow some line segments and return to the starting point. Every point can be reached more than once, but every segment can be painted at most once. To make the picture look interesting, different segments must be painted different colors. For each segment, Laura has already decided a direction to paint it. The picture below illustrates a possible way to paint the picture (dashed lines are segments that are not painted).

After you finish painting, your score is computed as follows: for each unit length you paint, you earn x points, for each color you use, you lost y points (Laura has prepared enough water pens of different colors).

Write a program to find the maximal score you can get.

输入:

The input contains several test cases. The first line of each case contains three positive integers n, x, y (1<=n<=100, 1<=x, y<=1000) . The next n lines each describe a point (points are numbered from 1 to n in the order they appear in the input). The first two integers (x, y) specify its coordinates (0<=x, y<=1000) . The rest integers are the points it connects to, ended by a zero. If point v appears in the list of point u , there is a line segment connecting u and v (then there will not a segment connecting u and v in the reverse direction). Furthermore, Laura will paint it from u to v . There will be no duplicated points and no more than 500 segments. The last test case is followed by a single zero, which should not be processed.

输出:

The input contains several test cases. The first line of each case contains three positive integers n, x, y (1<=n<=100, 1<=x, y<=1000) . The next n lines each describe a point (points are numbered from 1 to n in the order they appear in the input). The first two integers (x, y) specify its coordinates (0<=x, y<=1000) . The rest integers are the points it connects to, ended by a zero. If point v appears in the list of point u , there is a line segment connecting u and v (then there will not a segment connecting u and v in the reverse direction). Furthermore, Laura will paint it from u to v . There will be no duplicated points and no more than 500 segments. The last test case is followed by a single zero, which should not be processed.

样例输入:

4 5 1 
0 0 2 3 0 
1 0 3 4 0 
1 1 4 0 
0 1 1 0 
1 2 1 
0 0 0 
10 7 2 
0 0 2 4 0 
5 0 3 0 
5 10 4 10 0 
2 3 5 0 
7 5 6 0 
0 11 1 0 
8 0 10 5 0 
18 3 7 0 
14 5 8 1 0 
12 9 9 0 
0

样例输出:

Case 1: 16.00 
Case 2: 0.00 
Case 3: 522.18


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。