USACO07DEC道路建设Building Roads（prim算法+堆优化与Kruskal+路径压缩对比）

P2872 [USACO07DEC]道路建设Building Roads

4 1
1 1
3 1
2 3
4 3
1 4

4.00

时间上：
$Prim$Prim 适合稠密图，复杂度为 $O\left(n^2\right)$O(n2)
，因此通常使用邻接矩阵储存；但是堆优化为 $O\left(nlogn\right)$O(nlogn) 。

稠密图 $Prim$Prim 优于 $Kruskal$Kruskal ，稀疏图 $Kruskal$Kruskal 优于 $Prim$Prim 。

空间上：
$Prim$Prim 适合点少边多， $Kruskal$Kruskal 适合边多点少。

注意：堆优化的 $Prim$Prim 用空间换时间，空间要求更高。

看到下图两种方法比较：
$prim:$prim:

$kruskal:$kruskal:

需要注意的是：

C++11里double的输入是 %lf，输出是%f,double的用 %lf输出会为0.0000 ！

$prim$prim算法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//注意堆排序默认比较的是pair里的first
typedef pair<double,ll>pdl;
ifstream in("input.txt");
ofstream out("output.txt");
#define debug(x) cerr<<"# "<<x<<endl
const ll N=10005;
const ll base=137;
const ll mod=2147483647;
//const double INF=double(0x7f7f7f7f*1.0);
const double INF=double(INT_MAX*1.0);//要记得是double的
ll n,m;
double ans;
struct node
{
    ll x,y;
    double operator+(const node& a)const
    {
        return sqrt((double)(x-a.x)*(double)(x-a.x)+(double)(y-a.y)*(double)(y-a.y));
    }
}a[N];
double edge[N][N];
bool visit[N],done[N][N];
double dis[N];

void build(void)
{
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            if(!done[i][j])
                edge[j][i]=edge[i][j]=a[i]+a[j];
}

void input(void)
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            edge[i][j]=-1.0;//没修是-1
    for(int i=1;i<=n;++i)
        scanf("%lld %lld",&a[i].x,&a[i].y);
    for(int i=1;i<=m;++i)
    {
        ll u,v;
        scanf("%lld %lld",&u,&v);
        done[v][u]=done[u][v]=true;
        //修了是0题目中求的是需要新修的路的最小值
        //已经修好了的就按0计算（因为不用再修了）
        edge[u][v]=edge[v][u]=0;
    }
}
void prim(void)
{
    for(int i=1;i<=n;++i)
        dis[i]=INF;
    priority_queue<pdl,vector<pdl>,greater<pdl> >q;\
    q.push(pdl(0,1));//距离和农场编号
    dis[1]=0;//千万别忘了初始化一个起点！
    ll step=0;//记录一共加了几条边
    while(!q.empty()&&step<n)//最多修n-1条边
    {
        const double distances=q.top().first;
        const ll u=q.top().second;
        q.pop();
        if(visit[u])
            continue;
        visit[u]=true;
        ans+=distances;
        step++;
        for(int v=1;v<=n;++v)
        {
            //判断edge[u][v]是否等于-1.0是为了排除掉自己到自己
            if(edge[u][v]!=-1.0&&dis[v]>edge[u][v])
            {
                dis[v]=edge[u][v];
                q.push(pdl(dis[v],v));
            }
        }
    }
}
int main()
{
    input();
    build();
    prim();
    printf("%.2f",ans);
    return 0;
}

$Kruskal$Kruskal算法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,ll>pdl;
ifstream in("input.txt");
ofstream out("output.txt");
#define debug(x) cerr<<"# "<<x<<endl
const ll N=1005;
const ll base=137;
const ll mod=2147483647;
const double INF=double(0x7f7f7f7f*1.0);
//const double INF=double(INT_MAX*1.0);
ll n,m;
struct point
{
    ll x,y;
    double operator+(const point& a)const
    {
        return double(sqrt(double(x-a.x)*double(x-a.x)+double(y-a.y)*double(y-a.y)));
    }
}a[N];

struct node
{
    ll from,to;
    double v;
    bool operator<(const node& a)const
    {
        return (v!=a.v)?(v<a.v):(from<a.from);
    }
}edge[N*N];//邻接表
ll f[N];
double ans;
ll cnt;
bool done[N][N];
inline void build(void)//建路
{
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            if(!done[i][j])
                edge[++cnt]=(node){i,j,a[i]+a[j]};
}
inline void input()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lld %lld",&a[i].x,&a[i].y);
    for(int i=1;i<=m;++i)
    {
        ll x,y;
        scanf("%lld %lld",&x,&y);
        done[x][y]=done[y][x]=true;
        edge[++cnt]=(node){x,y,0};
    }
}
inline ll Find(const ll & x)
{
    return f[x]==x?x:f[x]=Find(f[x]);
}
inline void kruskal()
{
    ll step=0;
    for(int i=1;i<=n;++i)
    {
        f[i]=i;
    }
    sort(edge+1,edge+1+cnt);
    for(int i=1;i<=cnt;++i)
    {
        const ll u=Find(edge[i].from);
        const ll v=Find(edge[i].to);
        if(u==v)//如果不是一个集合的就可以走
            continue;
        ans+=edge[i].v;
        f[u]=v;//直接手动连上
        step++;
        if(step==n-1)//总共n-1条边
            return ;
    }
}
int main()
{
    input();
    build();
    kruskal();
    printf("%.2f\n",ans);
    return 0;
}