模板题（最短生成树prim算法）

题目链接：HDOJ1875

#include<bits/stdc++.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Island
{
    int x;
    int y;
}island;
double mmap[105][105];
island dao[105];
double distant(island *a,island *b)
{
   double  len;
   int ax=a->x;
   int ay=a->y;
   int bx=b->x;
   int by=b->y;

   int  temp=(ax-bx)*(ax-bx)+(ay-by)*(ay-by);
   len=sqrt(temp);

    if(len>1000||len<10)
        len=inf;
    return len;
}
int main()
{

    int T;//测试数
    int c;//小岛数

    int innum;//记录包含在生成树中的点的个数
    double route;//记录生成树长度
    double spend;//记录花费

    double dis[101];//记录所有顶点到当前生成树的最短路
    int tree[101];//记录结点是否已经包含在当前最短路中
   cin>>T;
  while(T--){
        cin>>c;
        fill(dis+1,dis+1+c,inf);//+1的原因是因为我们这里假设数组从下标1开始计数

        fill(tree+1,tree+1+c,0);//初始时生成树为空

        route=0;
        innum=0;
        spend=0;

        for(int i=1; i<=c; i++)
        {
            cin>>dao[i].x;
            cin>>dao[i].y;
        }
        //构图
        for(int i=1; i<=c; i++)
        {
            for(int j=i; j<=c; j++)
            {
                mmap[i][j]=mmap[j][i]=distant(&dao[i],&dao[j]);
            }
        }

        //最小生成树
        tree[1]=1;//先把1号点放入生成树
        for(int i=1; i<=c; i++)
        {
                dis[i]=mmap[1][i];
        }
        innum++;

        while(innum<c)
        {
            double mmin=inf;
            int nextin=0;//0号是一个特殊点（哨兵点），实际没有这个点
            for(int i=1; i<=c; i++)
            {
                if(tree[i]==0&&dis[i]<mmin)
                {
                    mmin=dis[i];
                    nextin=i;
                }
            }
            if(nextin==0)
                break;
            else
            {
                innum++;
                route+=mmin;//更新最小生成树的长度
                tree[nextin]=1;//把nextin放入生成树

                //更新dis数组
                for(int i=1; i<=c; i++)
                {
                    if(tree[i]==0&&mmap[nextin][i]<dis[i])
                        dis[i]=mmap[nextin][i];
                }
            }
        }


        if(innum!=c)
            cout<<"oh!"<<endl;
        else
        {
           spend=route*100;
           printf("%.1fn",spend);
        }

    }
    return 0;
}

最后

以上就是坦率乌龟为你收集整理的模板题（最短生成树prim算法）的全部内容，希望文章能够帮你解决模板题（最短生成树prim算法）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。