首页 > ACM题库 > HDU-杭电 > HDU 1614 Stacking Boxes-最小生成树-[解题报告] C++
2013
12-16

HDU 1614 Stacking Boxes-最小生成树-[解题报告] C++

Stacking Boxes

问题描述 :

Some concepts in Mathematics and Computer Science are simple in one or two dimensions but become more complex when extended to arbitrary dimensions. Consider solving differential equations in several dimensions and analyzing the topology of an n-dimensional hypercube. The former is much more complicated than its one dimensional relative while the latter bears a remarkable resemblance to its “lower-class” cousin.

Consider an n-dimensional “box” given by its dimensions. In two dimensions the box (2,3) might represent a box with length 2 units and width 3 units. In three dimensions the box (4,8,9) can represent a box 4*8*9(length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.

In this problem you will analyze a property of a group of n-dimensional boxes. You are to determine the longest nesting string of boxes, that is a sequence of boxesb1,b2,..bk such bi,that each box nests in box b(i+1)( 1≤i<k) .

A box D = ( d1,d2,…dn ) nests in a box E = ( e1,e2,…en ) if there is some rearrangement of the di, such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).

For example, the box D = (2,6) nests in the box E = (7,3) since D can be rearranged as (6,2) so that each dimension is less than the corresponding dimension in E. The box D = (9,5,7,3) does NOT nest in the box E = (2,10,6,8) since no rearrangement of D results in a box that satisfies the nesting property, but F = (9,5,7,1) does nest in box E since F can be rearranged as (1,9,5,7) which nests in E.

Formally, we define nesting as follows: box D = (d1,d2,….dn ) nests in box E = ( e1,e2,….en ) if there is a permutation π of 1..n such that ( ) “fits” in ( e1,e2…..en ) i.e., if for all 1≤i≤n.

输入:

The input consists of a series of box sequences. Each box sequence begins with a line consisting of the the number of boxes k in the sequence followed by the dimensionality of the boxes, n (on the same line.)

This line is followed by k lines, one line per box with the n measurements of each box on one line separated by one or more spaces. The i(th) line in the sequence ( 1<=i<=k ) gives the measurements for i(th) the box.

There may be several box sequences in the input file. Your program should process all of them and determine, for each sequence, which of the k boxes determine the longest nesting string and the length of that nesting string (the number of boxes in the string).

In this problem the maximum dimensionality is 10 and the minimum dimensionality is 1. The maximum number of boxes in a sequence is 30.

输出:

For each box sequence in the input file, output the length of the longest nesting string on one line followed on the next line by a list of the boxes that comprise this string in order. The “smallest” or “innermost” box of the nesting string should be listed first, the next box (if there is one) should be listed second, etc.

The boxes should be numbered according to the order in which they appeared in the input file (first box is box 1, etc.).

If there is more than one longest nesting string then any one of them can be output.

样例输入:

5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9

样例输出:

5
3 1 2 4 5
4
7 2 5 6

本题是求最小生成树的典型题目。

题目连接:http://acm.hit.edu.cn/hoj/problem/view?id=1614

采用Prim算法求最小生成树。

关于如何求球面上任意两点A(a1,b1)和 B(  a2,b2 ) 的球面距离,a1,a2是经度,b1,b2是纬度,参考公式:

r * acos(cos(a1 – a2) * cos(b1) * cos(b2) + sin(b1) * sin(b2))

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <math.h>
#include <algorithm>

using namespace std;

double p[102][2];
double map[102][102];
double dist[102];
int visited[102];

double r = 16.7/2;

//ai-经度,bi-纬度
double dis(double a1,double b1,double a2,double b2)
{

    a1 = acos(-1) * a1/180;
    b1 = acos(-1) * b1/180;
    a2 = acos(-1) * a2/180;
    b2 = acos(-1) * b2/180;

    return r * acos(cos(a1 - a2) * cos(b1) * cos(b2) + sin(b1) * sin(b2));
}
int main()
{

#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int n;
    int t = 0;
    while(scanf(" %d",&n)!=EOF && n!=0)
    {
        t++;
        for(int i = 0; i<n; i++)
        {
            scanf(" %lf %lf",&p[i][0],&p[i][1]);//经度、纬度
        }

        memset(map,0,sizeof(map));

        for(int i = 0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)
            {
                map[i][j] = map[j][i] = dis(p[i][0],p[i][1],p[j][0],p[j][1]);
            }
        }

        memset(dist,0x7f,sizeof(dist));
        memset(visited,0,sizeof(visited));
        dist[0] = 0;
        double sum = 0;

        for(int i=0; i<n; i++)
        {
            int k = 0;
            double min = 0x7f;
            //最短的dist[k]
            for(int j=0; j<n; j++)
            {
                if(visited[j] == 0 && dist[j]<min)
                {
                    min = dist[j];
                    k = j;
                }
            }
            visited[k] = 1;
            sum += min;
            //松弛该点
            for(int j = 0; j<n; j++)
            {
                if(dist[j] > map[k][j])
                {
                    dist[j] = map[k][j];
                }
            }

        }
        printf("Case %d: %.2lf miles\n",t,sum);
    }
    return 0;

}

解题报告转自:http://blog.csdn.net/niuox/article/details/8578573


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?