首页 > 代码库 > EOJ2067 最小生成树
EOJ2067 最小生成树
EOJ2067 最小生成树 prime算法和kruskal算法实现
题目：
Building Roads |
Time Limit:1000MS Memory Limit:30000KB
Total Submit:476 Accepted:144
Description
Farmer John had just acquired several new farms! He wants to connect the farmswith roads so that he can travel from any farm to any other farm via a sequenceof roads; roads already connect some of the farms.
Each of the N (1 <= N <= 1,000) farms (conveniently numbered 1..N) isrepresented by a position (X_i, Y_i) on the plane (0 <= X_i <=1,000,000;0 <= Y_i <= 1,000,000). Given the preexisting M roads(1 <= M <=1,000) as pairs of connected farms, help Farmer John
determine the smallest length of additional roads he must build to connect allhis farms.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Two space-separated integers: X_i and Y_i
* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating thatthere is already a road connecting the farm i and farm j.
Output
4 1
1 1
3 1
2 3
4 3
1 4
INPUT DETAILS:
Four farms at locations (1,1), (3,1), (2,3), and (4,3). Farms 1 and 4 areconnected by a road.
Sample Input
* Line 1: Smallest length of additional roads required to connect allfarms,printed without rounding to two decimal places. Be sure to calculate distancesas 64-bit floating point numbers.
Sample Output
4.00
OUTPUT DETAILS:
Connect farms 1 and 2 with a road that is 2.00 units long, then connect farms 3and 4 with a road that is 2.00 units long. This is the best we can do, andgives us a total of 4.00 unit lengths.
题目分析：
给定一些点的坐标，要在这些点间修路，一些点间的路已经修好，求最短的修路长度，使得图连通，最小生成树练习题。先预处理出所有点间的距离，然后把已经修好的点间的距离改成0。接下来可用prime算法和kruskal算法实现。1.prime算法思路类似dijkstra算法，每次选择到正在构建的生成树距离最短的点加入树的构建中，并通过新加入的点更新此集合与集合外各点的最小距离。2.kruskal算法每次取最短边来建树，且不能出现回路。
比较两个算法发现prime算法效率较高，因为当图接近完全图时，kruskal的复杂图比prime算法多了一个log（n*n）的常数。
两种实现代码如下：
1. prime算法：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
struct Node{
double x,y;
}node[1005];
double cost[1005][1005];
double low[1005];
bool vis[1005];
double dis(Node a,Node b){
returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double prime(int n){
int i,j,k;
double ans=0.0;
vis[1]=true;
for(i=2;i<=n;++i)
low[i]=cost[1][i];
for(i=1;i<=n-1;++i){
double minn=1000000000;
for(j=1;j<=n;++j){
if(!vis[j] &&minn>low[j]){
minn=low[j];k=j;
}
}
vis[k]=true;
ans+=low[k];
for(j=1;j<=n;++j){
if(!vis[j]){
low[j]=min(low[j],cost[k][j]);
}
}
}
return ans;
}
int main()
{
int n,m,i,j;
memset(vis,false,sizeof(vis));
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
scanf("%lf%lf",&node[i].x,&node[i].y);
for(i=1;i<=n;++i){
for(j=i+1;j<=n;++j){
cost[j][i]=cost[i][j]=dis(node[i],node[j]);
}
}
for(i=0;i<m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
cost[x][y]=cost[y][x]=0.0;
}
double ans=prime(n);
printf("%.2f\n",ans);
return 0;
}
2. kruscal算法：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct Node{
double x,y;
}node[1005];
struct E{
int pt1,pt2;
double length;
}e[1005*1005/2];
int set[1005];
int find(int x){
returnx==set[x]?x:(set[x]=find(set[x]));
}
double dis(Node a,Node b){
return(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(const E& a,const E& b){
return a.length<b.length;
}
double kruskal(int n,int k){
double ans=0.0;
int cnt=0,i;
for(i=0;i<k;++i){
intfx=find(e[i].pt1),fy=find(e[i].pt2);
if(fx==fy) continue;
set[fx]=fy;
ans+=sqrt(e[i].length);
++cnt;
if(cnt==n-1) break;
}
return ans;
}
int main()
{
int n,m,i,j,k=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
scanf("%lf%lf",&node[i].x,&node[i].y);
for(i=1;i<=n;++i){
for(j=1;j<=i-1;++j){
e[k].pt1=i;
e[k].pt2=j;
e[k++].length=dis(node[i],node[j]);
}
}
for(i=0;i<m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
if(x<y) swap(x,y);
// cout<<(x-2)*(x-1)/2+y-1<<endl;
e[(x-2)*(x-1)/2+y-1].length=0.0;
}
sort(e,e+k,cmp);
for(i=1;i<1005;++i)set[i]=i;
double ans=kruskal(n,k);
printf("%.2f\n",ans);
return 0;
}
EOJ2067 最小生成树