I - Swordfish(最小生成树）

题意：给定 $n$ 个点的坐标，求最小生成树。

思路：因为 $n$ 最大只有100，用 $kruskal$ 或者 $prim$ 都可以。

这里重新温习一下两个算法：

$kruskal:$ 对所有边排序，每次取最小边，取 $n-1$ 条边，同时用并查集维护当前图点的集合，如果不在集合里则加入该边。

时间复杂度: $O(mlogm)\ m$ 为边数。

$prim:$ 用一个数组 $d$ 维护当前子图与所有结点的最短距离。任取一结点开始，每次取与其相连的最短边的结点并加入，然后用该结点进行松弛当前子图到所有结点的最短距离.每次找到一条边，一共需要 $n-1$ 次。

朴素 $prim$ 复杂度： $O(n^2)$

与 $dijkstra$ 类似用优先队列实现的时间复杂度: $O(mlogn)$

$kruskal AC$ 代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=100+5;
#define mst(a) memset(a,0,sizeof a)
struct p{
    double x,y;
}a[N];
int s[N];
struct edge{
    int u, v;
    double w;
    bool operator<(const edge& a)const{
        return w<a.w;
    }
}e[N*N];
int find(int x){
    if(s[x]!=x) s[x]=find(s[x]);
    return s[x];
}
int main(){
    int n,k=0;
    while(~scanf("%d",&n)&&n){
        if(k) puts("");
        int id=0;
        double ans=0;
         for(int i=1;i<=n;i++){
             scanf("%lf%lf",&a[i].x,&a[i].y);
             s[i]=i;
             for(int j=1;j<i;j++){
                  double dis=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
                  dis=sqrt(dis);
                  e[++id]={i,j,dis};
             }
        }
         sort(e+1,e+id+1);
         int cnt=0;
         for(int i=1;i<=id;i++){
              int fa=find(e[i].u),fb=find(e[i].v);
              if(fa==fb) continue;
              cnt++;
              s[fb]=fa;
              ans+=e[i].w;
              if(cnt==n-1) break;
         }
         printf("Case #%d:\n",++k);
         printf("The minimal distance is: %.2lf\n",ans);
    }
    return 0;
}

$prim:AC$ 代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e2+5;
const double inf=1e15;
#define mst(a) memset(a,0,sizeof a)
double a[N][N];
struct p{
    double x,y;
}b[N];
int n,k;
double prim(){
    double d[N]={},ans=0;
    int vis[N]={};
    for(int i=1;i<=n;i++) d[i]=a[1][i];
    vis[1]=1;
    for(int i=2;i<=n;i++){
         double mn=inf;
         int p=0;
         for(int j=1;j<=n;j++)
             if(!vis[j]&&mn>d[j]) mn=d[j],p=j;
         if(mn==inf) break;
         ans+=mn,vis[p]=1;
         for(int j=1;j<=n;j++)    
             if(!vis[j]&&a[p][j]<d[j]) d[j]=a[p][j];
    }
    return ans;
}
int main(){
    while(~scanf("%d",&n)&&n){
        if(k) puts("");
        for(int i=1;i<=n;i++){
            scanf("%lf%lf",&b[i].x,&b[i].y);
            for(int j=1;j<i;j++)
               a[j][i]=a[i][j]=hypot(b[i].x-b[j].x,b[i].y-b[j].y);
        }
        printf("Case #%d:\n",++k);
        printf("The minimal distance is: %.2lf\n",prim());
     }
    return 0;
}