【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)。--这段分析有待考证。。。

目录
相关文章
|
1天前
|
Java
hdu-1874-畅通工程续(dijkstra + SPFA )
hdu-1874-畅通工程续(dijkstra + SPFA )
3 0
|
1天前
|
Java
hdu-2544-最短路(SPFA)
hdu-2544-最短路(SPFA)
5 0
|
6月前
|
算法 C++
用prim和kruskal算法求最小生成树问题
用prim和kruskal算法求最小生成树问题
48 0
|
算法 调度
最小生成树(Prim、Kruskal)算法,秒懂!
在数据结构与算法的图论中,(生成)最小生成树算法是一种常用并且和生活贴切比较近的一种算法。但是可能很多人对概念不是很清楚,什么是最小生成树?
138 0
最小生成树(Prim、Kruskal)算法,秒懂!
HDU-1874,畅通工程续(Floyd最短路)
HDU-1874,畅通工程续(Floyd最短路)
|
存储 定位技术 C++
【PTA】龙舌兰酒吧 (BFS求双源最短路)
【PTA】龙舌兰酒吧 (BFS求双源最短路)
132 0
【PTA】龙舌兰酒吧 (BFS求双源最短路)
|
算法
Prim Algoritm(最小生成树)
Prim Algorithm。这个算法可以分为下面几个步骤: 将顶点集V分成两个集合A和B,其中集合A表示目前已经在MST中的顶点,而集合B则表示目前不在MST中的顶点。 在B寻找与集合A连通的最短的边(u,v),将这条边加入最小生成树中。
847 0