首页 > ACM题库 > HDU-杭电 > HDU 2810-Hyperspace[解题报告]HOJ
2014
02-17

HDU 2810-Hyperspace[解题报告]HOJ

Hyperspace

问题描述 :

Hyperspace ,A Euclidean space of dimension greater than three (the original meaning of the word hyperspace, common in late nineteenth century British books, sometimes used in paranormal context, but which has become rarer since then). Minkowski space, a concept, often referred to by science fiction writers as hyperspace that refers to the four-dimensional space-time of special relativity.

Here we define a “Hyperspace” as a set of points in three-dimensional space. We define a function to describe its “Hyperspace Value”

Every vi (0<=i<=k) could be describe in three-dimensional reference system, say v0 (1, 2, 3)
For the following question, we will have to deal with the “Hyperspaces”, you may assume that the number of “Hyperspace” is always no larger than 100.
As we say above, we give every “Hyperspace” an “ID” to identify it.
If you want to connect two points in two different “Hyperspaces”, it will cost you F to build the connection. F can be defined as the following expression:

In addition, you can only create at most one connection between any two “Hyperspaces”.
If you want to connect two points in the same “Hyperspaces” whose “ID” is k, it will cost you G to build the connection. G can be defined as the following expression:

Here

Now your task is quite easy.
AekdyCoin gives you n “Hyperspaces”.
Then he gives you information about all the points in the “Hyperspaces”
Now he wants to know the minimal cost to connect all the points in all “Hyperspaces” you have to ensure that any two different points in the same “Hyperspace” could be connected directly or indirectly by the connections you build in this “Hyperspace”.

输入:

The input consists of several test cases.
In the first line there is an integer n (1<=n<=100), indicating the number of “Hyperspaces”
Then follow an integer m (1<=m<=100000)
You can assume that the number of different points in every “Hyperspace” is always no larger than 100.
The next m lines contain the descriptions of all the points
All the descriptions are given in the following format x,y,z,id
Indicating the point (x,y,z) belongs to the id “Hyperspace”
id is an integer.
x,y,z are all real number with at most four fractional digits.
-10000<=x,y,z<=10000,1<=id<=n

输出:

The input consists of several test cases.
In the first line there is an integer n (1<=n<=100), indicating the number of “Hyperspaces”
Then follow an integer m (1<=m<=100000)
You can assume that the number of different points in every “Hyperspace” is always no larger than 100.
The next m lines contain the descriptions of all the points
All the descriptions are given in the following format x,y,z,id
Indicating the point (x,y,z) belongs to the id “Hyperspace”
id is an integer.
x,y,z are all real number with at most four fractional digits.
-10000<=x,y,z<=10000,1<=id<=n

样例输入:

1
2
1 2 1 1
1 3 1 1

样例输出:

1.0000

刚拿到题目,就想到将集合看成一个独立点,求次MST。再对每个集合内的所有点求MST..

可惜比赛的时候没过这题。。错误原来在 空的集合 是不需要连接(这个没考虑所以出错了)
我用了prim算法 没什么优化..903ms过的.(可以用堆优化下)

#include<iostream>
#include<cmath>
using namespace std;
const double inf= 1000000000;
double math[105][105],matx[105][105];
struct point
{
    double x,y,z;
};
point hy[105][105];
int num[105],coll[105];
bool eq(point e,point d)
{
    if(abs(e.x-d.x)<1e-6&&abs(e.y-d.y)<1e-6&&abs(e.z-d.z)<1e-6)
        return true;
    return false;
}
double prim(double mat[][105],int n)
{
    double dist[105];
    bool visit[105];
    for(int i=0;i<n;i++)
        dist[i]=inf;
    memset(visit,false,sizeof(visit));
    dist[0]=0;
    double sum=0;
    for(int i=0;i<n;i++)
    {
        int minpos=-1;double minv=inf;
        for(int j=0;j<n;j++)
        {
            if(!visit[j]&&(minpos==-1||dist[j]<minv))
            {
                minpos=j;
                minv=dist[j];
            }
        }
        visit[minpos]=true;
        sum+=dist[minpos];
        for(int j=0;j<n;j++)
        {
            if(!visit[j]&&dist[j]>mat[minpos][j])
                dist[j]=mat[minpos][j];
        }
    }
    return sum;
}
int main()
{
    int n,m;
    while(cin>>n)
    {
        cin>>m;
        memset(num,0,sizeof(num));
        for(int i=0;i<m;i++)
        {
            point d;
            int id,j;
            cin>>d.x>>d.y>>d.z>>id;
            for(j=0;j<num[id-1];j++)
            {
                if(eq(hy[id-1][j],d)) break;
            }
            if(j==num[id-1])
            {
                hy[id-1][num[id-1]]=d;
                num[id-1]++;
            }
        }
        memset(math,0,sizeof(math));
        int len=0;
        for(int i=0;i<n;i++)
            if(num[i]!=0)
                coll[len++]=i;
        for(int i=0;i<len;i++)
            for(int j=0;j<len;j++)
                {
                    if(i==j)
                    {
                        math[i][j]=0;
                        continue;
                    }
                    math[i][j]=abs((double)(num[coll[i]]-num[coll[j]]))*abs((double)(coll[i]-coll[j]));
                }
        double sum=0;
        sum+=prim(math,len);
        for(int i=0;i<n;i++)
        {
            point it,it2;
            int l1,l2;
            memset(matx,0,sizeof(matx));
            for(l1=0;l1<num[i];l1++)
            {
                for(l2=0;l2<num[i];l2++)
                {
                    if(l1==l2)
                    {
                        matx[l1][l2]=0;
                        continue;
                    }
                    it=hy[i][l1];
                    it2=hy[i][l2];
                    double l=(it.x-it2.x)*(it.x-it2.x)+(it.y-it2.y)*(it.y-it2.y)+(it.z-it2.z)*(it.z-it2.z);
                    matx[l1][l2]=sqrt(l);
                }
            }
            double v=prim(matx,num[i]);
            sum+=v;
        }
        printf("%.4lf\n",sum);
    }
    return 0;
}

 


  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  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