【HDU 4463 Outlets】最小生成树(prim,kruscal都可)-阿里云开发者社区

开发者社区> helena_wang> 正文

【HDU 4463 Outlets】最小生成树(prim,kruscal都可)

简介: 以(x,y)坐标的形式给出n个点,修建若干条路使得所有点连通(其中有两个给出的特殊点必须相邻),求所有路的总长度的最小值。 因对所修的路的形状没有限制,所以可看成带权无向完全图,边权值为两点间距离。因是稠密图,故用邻接矩阵存储更好(完全图,边数e达到n(n-1)/2)。
+关注继续查看

以(x,y)坐标的形式给出n个点,修建若干条路使得所有点连通(其中有两个给出的特殊点必须相邻),求所有路的总长度的最小值。

因对所修的路的形状没有限制,所以可看成带权无向完全图,边权值为两点间距离。因是稠密图,故用邻接矩阵存储更好(完全图,边数e达到n(n-1)/2)。

至此,可将问题抽象为求最小生成树的边权和。

用了prim+邻接矩阵,prim+邻接表+堆,kruscal各写了一遍,只是内存稍有差别

对于所给的特殊的两个相邻点,只需在开始循环前把这两个点加入子树集合并更新它们所到达的点的mincost即可。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 const int MAX_N=55;
 7 const double INF=2000;
 8 
 9 struct Point
10 {
11     int x,y;
12 }a[MAX_N];
13 
14 double dis(Point& p1, Point& p2)
15 {
16     return sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
17 }
18 
19 int n;
20 int nike,apple;
21 double cost[MAX_N][MAX_N];//邻接矩阵(更适于稠密图)
22 double mincost[MAX_N];//集合到点i的最短距离
23 int used[MAX_N];
24 
25 double prim()
26 {
27     double res;
28     for(int i=0;i<n;i++)
29     {
30         mincost[i]=INF;
31         used[i]=0;
32     }//将nike,apple两个点加入集合,并更新它们所到达的点的mincost
33     mincost[nike]=mincost[apple]=0;
34     used[nike]=used[apple]=1;
35     res=cost[nike][apple];
36     for(int i=0;i<n;i++)
37     {
38         mincost[i]=min(mincost[i],cost[nike][i]);
39     }
40     for(int i=0;i<n;i++)
41     {
42         mincost[i]=min(mincost[i],cost[i][apple]);
43     }
44     while(1)
45     {
46         int v=-1;
47         for(int i=0;i<n;i++)//找到集合以外的mincost最小的点
48         {
49             if(!used[i]&&(v==-1||mincost[i]<mincost[v]))
50                 v=i;
51         }
52         if(v==-1) break;//不存在负权边
53         used[v]=1;
54         res+=mincost[v];//加入集合,更新它所到达的点
55         for(int i=0;i<n;i++)
56         {
57             mincost[i]=min(mincost[i],cost[i][v]);
58         }
59     }
60     return res;
61 }
62 
63 
64 int main()
65 {
66     //freopen("1011.txt","r",stdin);
67     while(scanf("%d",&n)!=EOF)
68     {
69         if(n==0) break;
70         scanf("%d%d",&nike,&apple);
71         nike--;
72         apple--;
73         for(int i=0;i<n;i++)
74         {
75             scanf("%d%d",&a[i].x,&a[i].y);
76         }
77         for(int i=0;i<n;i++)//求两点间距离,得到邻接矩阵
78         {
79             cost[i][i]=0;
80             for(int j=i+1;j<n;j++)
81                 cost[i][j]=cost[j][i]=dis(a[i],a[j]);
82         }
83         printf("%.2lf\n",prim());
84     }
85     return 0;
86 }
prim_邻接矩阵
  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <vector>
  4 #include <queue>
  5 #include <cmath>
  6 using namespace std;
  7 
  8 const int MAX_N=55;
  9 const double INF=2000;
 10 
 11 struct Point
 12 {
 13     int x,y;
 14 }a[MAX_N];
 15 
 16 double dis(Point& p1, Point& p2)
 17 {
 18     return sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
 19 }
 20 
 21 struct Edge
 22 {
 23     int to;
 24     double cost;
 25     Edge(){}
 26     Edge(int tt,double cc):to(tt),cost(cc){}
 27 };
 28 typedef pair<double,int> P;//cost,to
 29 int n;
 30 int nike,apple;
 31 double dis_na;
 32 vector<Edge> G[MAX_N];
 33 double mincost[MAX_N];//集合到点i的最短距离
 34 int used[MAX_N];
 35 
 36 double prim()
 37 {
 38     double res=0;
 39     for(int i=0;i<n;i++)
 40     {
 41         mincost[i]=INF;
 42         used[i]=0;
 43     }//将nike,apple两个点加入集合,并将与它们相邻的边推入队列
 44     mincost[nike]=mincost[apple]=0;
 45     used[nike]=used[apple]=1;
 46     res=dis_na;
 47     priority_queue<P,vector<P>,greater<P> >que;
 48     for(int i=0;i<G[nike].size();i++)
 49     {
 50         int u=G[nike][i].to;
 51         if(used[u]||mincost[u]<G[nike][i].cost) continue;
 52         mincost[u]=G[nike][i].cost;
 53         que.push(P(mincost[u],u));
 54     }
 55     for(int i=0;i<G[apple].size();i++)
 56     {
 57         int u=G[apple][i].to;
 58         if(used[u]||mincost[u]<G[apple][i].cost) continue;
 59         mincost[u]=G[apple][i].cost;
 60         que.push(P(mincost[u],u));
 61     }
 62     while(!que.empty())
 63     {
 64         P p=que.top();
 65         que.pop();
 66         int v=p.second;
 67         if(used[v]||mincost[v]<p.first) continue;
 68         mincost[v]=p.first;
 69         used[v]=1;
 70         res+=mincost[v];//加入集合,更新它所到达的点
 71         for(int i=0;i<G[v].size();i++)
 72         {
 73             int u=G[v][i].to;
 74             if(!used[u]&&mincost[u]>G[v][i].cost)
 75             {
 76                 mincost[u]=G[v][i].cost;
 77                 que.push(P(mincost[u],u));
 78             }
 79         }
 80     }
 81     return res;
 82 }
 83 
 84 int main()
 85 {
 86     //freopen("4463.txt","r",stdin);
 87     while(scanf("%d",&n)!=EOF)
 88     {
 89         if(n==0) break;
 90         scanf("%d%d",&nike,&apple);
 91         nike--;
 92         apple--;
 93         for(int i=0;i<n;i++)
 94         {
 95             scanf("%d%d",&a[i].x,&a[i].y);
 96         }
 97         for(int i=0;i<n;i++) G[i].clear();
 98         for(int i=0;i<n;i++)//求两点间距离,得到表
 99         {
100             for(int j=i+1;j<n;j++)
101             {
102                 double temp=dis(a[i],a[j]);
103                 G[i].push_back(Edge(j,temp));
104                 G[j].push_back(Edge(i,temp));
105                 if(i==nike&&j==apple) dis_na=temp;
106             }
107         }
108         printf("%.2lf\n",prim());
109     }
110     return 0;
111 }
prim_邻接表_堆
  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cmath>
  4 using namespace std;
  5 
  6 const int MAX_N=55;
  7 
  8 int parent[MAX_N];
  9 int rankk[MAX_N];
 10 void init(int N)
 11 {
 12     for(int i=0;i<=N;i++)
 13     {
 14         parent[i]=i;
 15         rankk[i]=0;
 16     }
 17 }
 18 int find(int x)
 19 {
 20     if(x==parent[x]) return x;
 21     return parent[x]=find(parent[x]);
 22 }
 23 void unite(int x,int y)
 24 {
 25     x=find(x);
 26     y=find(y);
 27     if(x==y) return ;
 28     if(rankk[x]<rankk[y]) parent[x]=y;
 29     else
 30     {
 31         parent[y]=x;
 32         if(rankk[x]==rankk[y]) rankk[x]++;
 33     }
 34 }
 35 bool same(int x,int y)
 36 {
 37     return find(x)==find(y);
 38 }
 39 
 40 struct Point
 41 {
 42     int x,y;
 43 }a[MAX_N];
 44 
 45 double dis(Point& p1, Point& p2)
 46 {
 47     return sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
 48 }
 49 
 50 struct Edge
 51 {
 52     int from,to;
 53     double cost;
 54 }edges[MAX_N*MAX_N];
 55 
 56 bool cmp(Edge e1,Edge e2)
 57 {
 58     return e1.cost<e2.cost;
 59 }
 60 
 61 int n,m;
 62 int nike,apple;
 63 double dis_na;
 64 
 65 double kruscal()
 66 {
 67     double ans=0;
 68     init(n);
 69     unite(nike,apple);
 70     ans+=dis_na;
 71     for(int i=0;i<m;i++)
 72     {
 73         if(!same(edges[i].from,edges[i].to))
 74         {
 75             ans+=edges[i].cost;
 76             unite(edges[i].from,edges[i].to);
 77         }
 78     }
 79     return ans;
 80 }
 81 
 82 int main()
 83 {
 84     //freopen("4463.txt","r",stdin);
 85     while(scanf("%d",&n)!=EOF)
 86     {
 87         if(n==0) break;
 88         scanf("%d%d",&nike,&apple);
 89         nike--;
 90         apple--;
 91         for(int i=0;i<n;i++)
 92         {
 93             scanf("%d%d",&a[i].x,&a[i].y);
 94         }
 95         m=0;
 96         for(int i=0;i<n;i++)//求两点间距离,得到所有边
 97         {
 98             for(int j=i+1;j<n;j++)
 99             {
100                 double temp=dis(a[i],a[j]);
101                 edges[m].from=i;
102                 edges[m].to=j;
103                 edges[m].cost=temp;
104                 m++;
105                 if((i==nike&&j==apple)||(i==apple&&j==nike)) dis_na=temp;
106             }
107         }
108         sort(edges,edges+m,cmp);
109         printf("%.2lf\n",kruscal());
110     }
111     return 0;
112 }
kruscal_边数组

邻接矩阵版Prim算法求最小生成树,时间复杂度为O(n*n)。邻接表版prim用堆优化后理论上可达O(elogn),边数组版kruscal理论也为O(elogn),但此题是完全图,e=n(n-1)/2,故实为O(n*nlogn)>O(n*n)。--这段分析有待考证。。。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
into outfile 生成sql脚本
select concat('insert into t_dm_stage(STAGE_ID,STAGE_NAME) values(',STAGE_ID,',','\'',STAGE_NAME,'\'',');') into outfile '/tmp/sql.txt' from t_dm_stage; 会在mysql服务器的/tmp/目录下生成一个sql.txt文件。
666 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10096 0
hdu4750Count The Pairs(最小生成树找瓶颈边)
1 /* 2 题意:就是给你一个图,图的每两个点都有多条路径,每一条路径中都有一条最大边, 3 所有最大边的最小边(也就是瓶颈边)就是这两点之间的val值!然后给你一个值f, 4 问有多少个顶点对的val>=f! (u,v) 和 (v, u)是不同的顶点对! ...
467 0
最小生成树——Prim算法
最小生成树是图这一数据结构里最常讨论的方面之一。   先用一下几个概念回忆一下什么是最小生成树:         连通图:任意两个结点之间都有一个路径相连         生成树(Spannirng Tree):连通图的一个极小的连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边         最小生成树(Minimum Spannirng Tree):连通图的最小代价的生成树(各边的权值之和最小)   最小生成树性质(MST性质):         设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。
875 0
Intellij idea使用postgresql 反向生成实例, 'Basic' attribute type should not be 'Object'
mapped type不能Object? 本人使用 intellij idea 15 , postgresql 9.4,在开发java ee 。 在用 Hibernate时, 需要用数据库表反向生成实例,数据库中部分字段,是Int4,在反转的时候会爆出错误,下面是我的测试图,有木有大牛了解,可不可给给点解决方法,【生成后手动一个个修改回来除外】,各种google过……唉,求教....   下拉框中并没有String或Integer 的选项,只有Object和序列化两种。
1135 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
12078 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13894 0
.net中生成excel后调整宽度
 生成excel后加上    _Worksheet ActiveSheet;         //_Chart ActiveChart;         _Workbook oBook;         _Application oExcel = new ApplicationClass();         oExcel.
535 0
Couchdb装好,却无法使用Futon,或者无法生成View
昨天装好了Couchdb-1.0.2,用couchdb -b启动正常,用curl http://127.0.0.1:5984/也能收到欢迎信息,却打不开网页客户端Futon。 想起之前也碰到这样的问题,第二天自己好了,就把Linux重启了一下,解决了!应该是某个依赖的进程需要重启,猜测是js spidemokey。
925 0
+关注
helena_wang
&quot;The master has failed more times than the beginner has even tried.&quot;
59
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载