本题是 最小生成树，用prim 比较方便，用kruskal的话，我超时了，看了discuss 后才知道要用优先队列 优化。而且这题 prim 效率应该效率更高。
kruskal +优先队列
Memory: 8032K Time: 125MS
Language: C++ Result: Accepted
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int N,M,set[1021],need,num;
double vx[1001],vy[1001];
struct edge
{
int x,y;
double w;
}e[555555];
int find (int x)
{
int i,j,r;
r=x;
while(set[r]!=r)
r=set[r];
j=x;
while(j!=r)
{
i=set[j];
set[j]=r;
j=i;
}
return r;
}
void merge(int x,int y)
{
if(x>y)
set[x]=y;
else set[y]=x;
}
void insert(edge a)
{
int i;
num++;
e[num]=a;
i=num;
while(i>1 && e[i].w<e[i/2].w)
{
swap(e[i],e[i/2]);
i=i/2;
}
}
void heapify(int i)
{
int l,r,small;
l=i*2;;
r=l+1;
small=i;
if(l<=num && e[small].w>e[l].w)
small=l;
if(r<=num && e[small].w>e[r].w)
small=r;
if(i!=small)
{
swap(e[i],e[small]);
heapify(small);
}
}
edge del()
{
edge min;
min=e[1];
swap(e[1],e[num]);
num--;
heapify(1);
return min;
}
double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double kruskal()
{
int sn,sm;
double sum=0;
edge temp;
for(int i=1;i<=N;i++)
for(int j=i+1;j<=N;j++)
{
sn=find(i);
sm=find(j);
if(sn!=sm)
{
temp.x=i;
temp.y=j;
temp.w=dis(vx[i],vy[i],vx[j],vy[j]);
insert(temp);
}
}
for(int i=1;i<=num;i++)
{
temp=del();
sn=find(temp.x);
sm=find(temp.y);
if(sn!=sm)
{
merge(sn,sm);
sum+=temp.w;
need--;
}
if(need==0)break;
}
return sum;
}
int main()
{
int n,m,count;
double total;
while(scanf("%d%d",&N,&M) !=EOF)
{
count=0;
for(int i=1;i<=N;i++)
{
scanf("%lf%lf",&vx[i],&vy[i]);
}
for(int i=1;i<=N;i++)
set[i]=i;
for(int i=1;i<=M;i++)
{
int sn,sm;
scanf("%d%d",&n,&m);
sn=find(n);
sm=find(m);
merge(sn,sm);
}
need=-1;
for(int i=1;i<=N;i++)
{
if(set[i]==i )need++;
}
total=kruskal();
printf("%.2lf\n",total);
num=0;
}
}
直接prim算法
Memory: 8052K Time: 94MS
Language: C++ Result: Accepted
#include<iostream>
#include<cmath>
using namespace std;
double map[1001][1001];
int N,M;
double prim()
{
bool vis[1001]={0};
double lw[1001],min,sum;
int k;
for(int i=1;i<=N;i++)
lw[i]=map[1][i];
vis[1]=1;
sum=0;
for(int i=1;i<N;i++)
{
min=10000001;
for(int j=1;j<=N;j++)
if(!vis[j] && lw[j]<min)
{
min=lw[j];
k=j;
}
sum+=min;
vis[k]=1;
for(int j=1;j<=N;j++)
if( !vis[j] && map[k][j]<lw[j])
lw[j]=map[k][j];
}
return sum;
}
double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
double vx[1001],vy[1001],total;
int n,m;
while(scanf("%d%d",&N,&M) !=EOF)
{
for(int i=1;i<=N;i++)
scanf("%lf%lf",&vx[i],&vy[i]);
for(int i=1;i<=N;i++)
for(int j=i+1;j<=N;j++)
{
double temp=dis(vx[i],vy[i],vx[j],vy[j]);
map[i][j]=map[j][i]=temp;
}
for(int i=1;i<=M;i++)
{
scanf("%d%d",&n,&m);
map[n][m]=map[m][n]=0;
}
total=prim();
printf("%.2lf\n",total);
}
}
评论