hdu 1162 Eddy's picture (Kruskal算法,prim算法,最小生成树)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1162

【题目大意】

给你n个点的坐标,让你找到联通n个点的一种方法,保证联通的线路最短,典型的最小生成树问题。

方法一 , 通过不断找到最小的边来找到最终结果。

Kruskal 算法

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
struct node{
    double a,b;
    int po;
}point[110];
const int maxe = 10010;
struct Edge{
    int v1,v2;
    double length;
}edge[maxe];
bool cmp(const Edge&a, const Edge&b){
    return a.length<b.length;
}
int n; int cnt;
int father[110];
void MakeSet(){
    for(int i=0;i<=n;i++){
        father[i]=i;
    }
}
int Find(int x){
    int xroot = x;
    while(xroot!=father[xroot])
        xroot=father[xroot];
    while(x!=xroot){
        int tmp = father[x];
        father[x]=xroot;
        x = tmp;
    }
    return xroot;
}
void Union(int x,int y){
    int xr=Find(x);
    int yr=Find(y);
    if(xr==yr) return ;
    else{
        father[xr]=yr;
    }
}
void Kruskal(){
    int edgenum=0;
    double ans=0;
    for(int i=0;i<cnt&&edgenum!=n-1;i++){
        if(Find(edge[i].v1)!=Find(edge[i].v2)){
            ans+=edge[i].length;
            Union(edge[i].v1,edge[i].v2);
            edgenum++;
        }
    }
    printf("%.2lf\n",ans);
}
double disc(node x, node y){
    return (double)sqrt((x.a-y.a)*(x.a-y.a)+(x.b-y.b)*(x.b-y.b));
}
int main(){
    double a,b;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>point[i].a>>point[i].b;
            point[i].po=i+1;
        }
        MakeSet();
        cnt=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                double dis= disc(point[i],point[j]); //求出点 与 点 之 间 的距 离, 列出所有的边。
                edge[cnt].v1=point[i].po;
                edge[cnt].v2=point[j].po;
                edge[cnt].length=dis;
                cnt++;
            }
        }
        sort(edge,edge+cnt,cmp);
        Kruskal();
    }
    return 0;
}

方法二 prim算法, 通过不断找到距离 最小生成树所在集合所有点中 距离最小的点。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
#define maxn 110
#define INF 0xfffffff
struct node{
	double a,b;
	int po;
}point[maxn];
int n;
struct node2{
	int v;
	double dis;
	node2(int v=0, double dis=0):v(v),dis(dis){}
};
vector <node2> G[maxn]; //用邻接链表储存图
const int maxe = 10010;
bool intree[maxn];
double minDist[maxn];
void init(){
	for(int i=0;i<maxn;i++ ){
		minDist[i]=INF;
		G[i].clear();
		intree[i]=false;
	}
}
double prim(int s){
	intree[s] = true;
	for(int i=0;i<G[s].size();i++){
		int vex = G[s][i].v;
		minDist[vex] = G[s][i].dis; //初始化  , 将与起点相联的 点与起点的距离“显化”
	}
	double ans = 0;
	for(int nodeNum = 1 ;nodeNum<=n-1;nodeNum++){ //还剩下 n-1 个点未找
		double tmpMin = INF;
		int addNode;
		for(int i=1;i<=n;i++){
			if(!intree[i]&&minDist[i]<tmpMin){ //只有经过显化的 且没有入最小生成树的点 才能通过比较
				tmpMin = minDist[i]; //不断更新,找到最短的
				addNode = i;
			}
		}
		intree[addNode] = true; //入树
		ans+=tmpMin;
		for(int i=0; i < G[addNode].size();i++){ //更新  将新加入节点的 相联节点“显化”
			int vex = G[addNode][i].v;
			if(!intree[vex]&&G[addNode][i].dis<minDist[vex]) //更新未入最小生成树的节点,与之的最短距离。
				minDist[vex] = G[addNode][i].dis;
		}
	}
	return ans;
}
double disc(node x, node y){
	return (double)sqrt((x.a-y.a)*(x.a-y.a)+(x.b-y.b)*(x.b-y.b));
}
int main(){
	double a,b;
	while(cin>>n){
		for(int i=0;i<n;i++){
			cin>>point[i].a>>point[i].b;
			point[i].po=i+1;
		}
		init();
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				double dis= disc(point[i],point[j]);
				G[point[i].po].push_back(node2(point[j].po,dis));
				G[point[j].po].push_back(node2(point[i].po,dis));
			}
		}
		double ans = prim(1);
		printf("%.2lf\n",ans);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

hdu 1162 Eddy's picture (Kruskal算法,prim算法,最小生成树)

时间: 08-11

hdu 1162 Eddy's picture (Kruskal算法,prim算法,最小生成树)的相关文章

hdu 1162 Eddy&#39;s picture 最小生成树入门题 Prim+Kruskal两种算法AC

Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7428    Accepted Submission(s): 3770 Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to

HDU 1162 Eddy&#39;s picture【最小生成树,Prime算法+Kruskal算法】

Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9334    Accepted Submission(s): 4711 Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to

hdu 1162 Eddy&#39;s picture(最小生成树算法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1162 Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6866    Accepted Submission(s): 3469 Problem Description Eddy begins to like p

HDU 1162 Eddy&#39;s picture (最小生成树 prim)

题目链接 Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the res

HDU 1162 Eddy&#39;s picture (prime算法_裸题)

Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the result i

hdu 1162 Eddy&#39;s picture (prim)

Eddy's pictureTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 11970    Accepted Submission(s): 6008 Problem DescriptionEddy begins to like painting pictures recently ,he is sure of himself to be

HDU 1162 Eddy&#39;s picture(图论-最小生成树)

题目如下: Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7267    Accepted Submission(s): 3676 Problem Description Eddy begins to like painting pictures recently ,he is sure of himse

题解报告:hdu 1162 Eddy&#39;s picture

Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the result i

hdu 1162 Eddy&#39;s picture

最小生成树裸题,没有初始化都能AC,看来测试数据只有一组 #include<iostream> #include<vector> #include<cmath> #include<cstdio> #define inf 1<<30 #define maxn 105 using namespace std; struct stu { double x,y; }; stu mapp[maxn]; int n; vector<int>roo