首页 > ACM题库 > HDU-杭电 > HDU 1046 Gridland[解题报告] C++
2013
11-26

HDU 1046 Gridland[解题报告] C++

Gridland

问题描述 :

For years, computer scientists have been trying to find efficient solutions to different computing problems. For some of them efficient algorithms are already available, these are the “easy” problems like sorting, evaluating a polynomial or finding the shortest path in a graph. For the “hard” ones only exponential-time algorithms are known. The traveling-salesman problem belongs to this latter group. Given a set of N towns and roads between these towns, the problem is to compute the shortest path allowing a salesman to visit each of the towns once and only once and return to the starting point.

The president of Gridland has hired you to design a program that calculates the length of the shortest traveling-salesman tour for the towns in the country. In Gridland, there is one town at each of the points of a rectangular grid. Roads run from every town in the directions North, Northwest, West, Southwest, South, Southeast, East, and Northeast, provided that there is a neighbouring town in that direction. The distance between neighbouring towns in directions North�South or East�West is 1 unit. The length of the roads is measured by the Euclidean distance. For example, Figure 7 shows 2 × 3-Gridland, i.e., a rectangular grid of dimensions 2 by 3. In 2 × 3-Gridland, the shortest tour has length 6.

输入:

The first line contains the number of scenarios.

For each scenario, the grid dimensions m and n will be given as two integer numbers in a single line, separated by a single blank, satisfying 1 < m < 50 and 1 < n < 50.

输出:

The output for each scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. In the next line, print the length of the shortest traveling-salesman tour rounded to two decimal digits. The output for every scenario ends with a blank line.

样例输入:

2
2 2
2 3

样例输出:

Scenario #1:
4.00

Scenario #2:
6.00

题目大意:就是给你一个题目上的那种图,问你从起点出发,最后回到起点的最短路程

解法:

尼玛,我画了一下,我说怎么这么水,我直接把路程算成n*m交了,WR了。。。因为我把斜线的长度也看成1了。。。

在n跟m都是奇数的时候,需要走一次斜线,所以路程是n*m+sqrt(2)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int T;cin>>T;
    int k=1;
    int n,m;
    while (T--)
    {
        cin>>n>>m;
        if(n&1 && m&1)
            printf("Scenario #%d:\n%.2f\n",k++,double(n*m+0.41));
        else printf("Scenario #%d:\n%d.00\n",k++,n*m);
        cout<<endl;
    }
    return 0;
}


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?