算法
最小生成树+prim
思路
既然这题本质上就是Prim算法, 我就在这里写一写我对Prim算法的理解.
两个最小生成树算法, 都有一个共同的思想: 这棵树是一点一点长大的; 并且每次生长, 都是贪心的.
不同之处是: Kruscal算法是以边为中心的, 每次找最小的并且有用的边添加到树上;
Prim算法是以点为中心的, 每次找离树最近的点添加到树上.
我们可以把一棵树理解成一个有智能的生命, 可以感知它附近的点到它的距离. 每次生长枝条, 它都选择离它最近的那个点.
点到树的距离, 是指树外一个点到树上的任意点的最小距离.
所以,在代码实现的时候, 需要维护这样一个数组: 树外的点到树的距离. 所以, 还需要区分一下点究竟在树上还在树外.
维护数组就是要做两件事: 更改数组和调用数组.
何时更改: 树外的点到树的距离发生变化. 这种事只能在树生长了新的枝条的时候发生, 因为新加入的那个点可能更新了树到树外的某个点的距离. 同时, 新加入的那个点变成了树上的点.
何时调用: 想扩张的时候, 找最近的树外点.
一开始, 我们认为1号结点在树上, 把它到树的距离设为0; 其它结点的距离是INF.
在调用完整个算法之后, 因为当一个节点变成树上节点后, 我们就不再更新它到树的距离, 所以, 原来的数组记录的就是它加入到树上时的连边长度. 对之求和, 就是树上所有边权之和.
Prim算法的优势: 稠密图, 尤其是完全图. 因为在Kurscal算法中, 必须事先求出所有边的长度才能对之排序. 但是一个有5000节点的完全图, 这样做的空间开销是巨大的. Prim算法只在更新点到树的距离时需要用到边长, 因此对于这种给坐标的完全图, 可以现用现算.
代码
#include<bits/stdc++.h>
#define For(i, m) for(register int i=1; i<=m; i++)
#define INF 0x3f
#define N 5123
#define M
using namespace std;
struct POINT{
long long x;
long long y;
long long operator* (const POINT &b) const {
return (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
}
}city[N];
inline long long read(){
long long x=0, sign=1; char c=getchar();
while(c>'9' || c<'0') {if (c=='-') sign=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*sign;
}
int n, m;
bool v[N]; long long d[N];
void prim(){
memset(d, INF, sizeof(d));
memset(v, 0, sizeof(v));
d[1]=0;
For(i, n-1){
int x=0;
For(j, n){
if (!v[j] && (x==0 || d[j]<d[x])) x=j;
}
v[x]=1;
For(y, n){
if (!v[y]) d[y]=min(d[y], city[x]*city[y]);
}
}
}
int main(){
n=read();
For(i, n){
city[i].x=read();
city[i].y=read();
}
prim();
double ans=0;
For(i, n) ans+=sqrt((double)d[i]);
printf("%.2f
", ans);
return 0;
}