剛拿到題目，就想到將集合看成一個獨(dú)立點(diǎn)，求次MST。再對每個集合內(nèi)的所有點(diǎn)求MST..
可惜比賽的時候沒過這題。。錯誤原來在 空的集合 是不需要連接(這個沒考慮所以出錯了)
我用了prim算法 沒什么優(yōu)化..903ms過的.(可以用堆優(yōu)化下)
#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;
}
posted on 2009-05-02 20:37
米游 閱讀(386)
評論(0) 編輯 收藏 引用 所屬分類:
ACM