1002.cpp

HDOJ 5月2日 “老菜鸟杯”程序大赛标准程序+解题报告

#include <iostream>
#include <vector>
#include <cmath>
#include <time.h>
using namespace std;

const int POINT_MAX=10005;
const int SIZE=17389;
const int BUFFER=10000;

struct D_Point
{
    double x,y,z;
};

struct Point
{
    int x,y,z;
    bool operator==(const Point&p)
    {
        return (x==p.x && y==p.y && z==p.z);
    }
};

//============Hash===================

struct HashNode
{
    Point cur;
    int next;
};

HashNode Hash_Table[SIZE+BUFFER];
bool flag[SIZE];
int top;

void Hash_Init()
{
    memset(flag,0,sizeof(flag));
    top=SIZE;
}

int hash(const Point&p)
{
    int ans=(p.x+p.y+p.z+p.x*p.y*p.z)%SIZE;
    if (ans<0) ans+=SIZE;
    return ans;
}

void insert(const Point&p)
{
    int key=hash(p);
    if (!flag[key])
    {
        flag[key]=true;
        Hash_Table[key].cur=p;
        Hash_Table[key].next=-1;
        return ;
    }
    else
    {
        while (true)
        {
            if (Hash_Table[key].cur==p)
                return;
            if (Hash_Table[key].next==-1) break;
            key=Hash_Table[key].next;
        }

        Hash_Table[key].next=top;
        Hash_Table[top].cur=p;
        Hash_Table[top].next=-1;
        top++;
    }
}

bool query(const Point&p)
{
    int key=hash(p);

    if (!flag[key])
        return false;
    else
    {
        while (true)
        {
            if (Hash_Table[key].cur==p)
                return true;
            if (Hash_Table[key].next==-1) return false;
            key=Hash_Table[key].next;
        }
    }
}


//============Hash===================


double Distance(D_Point a,D_Point b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}


int n,m;
vector<D_Point> hyper[105];
double g[105][105];
int id[105];
double d[105];
bool has[105];
vector<int>number;


//Prim
double Prim(int N,double g[105][105])
{
    int top=N-1;
    int i,j;
    double ans=0.0;

    for (i=1;i<N;i++)
    {
        d[i]=g[0][i];
        id[i-1]=i;
    }

    for (i=0;i<N-1;i++)
    {
        int cur,pos=0;
        for (j=1;j<top;j++)
        {
            if (d[id[j]]<d[id[pos]])
                pos=j;
        }

        cur=id[pos];
        ans+=d[cur];

        id[pos]=id[--top];

        for (j=0;j<top;j++)
            if (d[id[j]]>g[id[j]][cur])
            {
                d[id[j]]=g[id[j]][cur];
            }
    }

    return ans;
}


double Calc(const vector<D_Point>&hyperspace)
{
    int n=hyperspace.size();
    int i,j;
    double res=0.0;

    if (n)
    {
        for (i=0;i<n;i++)
            for (j=0;j<n;j++)
                g[i][j]=Distance(hyperspace[i],hyperspace[j]);

        res=Prim(n,g);
    }

    return res;
}

int main()
{
    int i,j;
    Point cur;
    D_Point p;
    int id;
    double ans;
	int cnt;

    OPEN
    clock_t A=clock();
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        ans=0;
		 number.clear();
        for (i=0;i<n;i++)
        {
            hyper[i].clear();
            has[i]=false;
        }

        Hash_Init();

        for (i=0;i<m;i++)
        {
            scanf("%lf%lf%lf%d",&p.x,&p.y,&p.z,&id);
            id--;
            cur.x=(int)(p.x*10000+0.5);
            cur.y=(int)(p.y*10000+0.5);
            cur.z=(int)(p.z*10000+0.5);

            if (!query(cur))
            {
                insert(cur);
                hyper[id].push_back(p);
            }
        }

        for (i=0;i<n;i++)
        {
            if (hyper[i].size())
            {
                ans+=Calc(hyper[i]);
                has[i]=true;
            }
        }


        for (i=0;i<n;i++)
			if (has[i])
			{
				number.push_back(i);
			}

		cnt=number.size();

        for (i=0;i<cnt;i++)
            for (j=0;j<cnt;j++)
            {
                g[i][j]=fabs((double)hyper[number[i]].size()-hyper[number[j]].size())*fabs(1.0*number[i]-number[j]);
            }

        ans+=Prim(cnt,g);
        printf("%.4lf\n",ans);
    }
    printf("%dms\n",clock()-A);
    return 0;
}