Freckles

#include<iostream>
#include<cmath>
using namespace std;
struct Point//定义点集
{
    double x;
    double y;
};
int main()
{
    Point point[500];
    int n;//点的个数
    int cnt = 0;//已访问的点个数
    double minSum = 0;//最小的距离和
    double mapInfo[500][500];//用于储存点集距离信息
    double distanceToTree[500];//到最小生成树的距离信息
    cin >> n;//输入点的信息
    for (int i = 1; i <= n; i++)
    {
        cin >> point[i].x >> point[i].y;
    }
    for (int i = 1; i <= n; i++)//计算点与点之间的距离信息
    {
        for (int j = i; j <= n; j++)
        {
            if (i == j)
                mapInfo[i][j] = mapInfo[j][i] = 0;
            else
                mapInfo[i][j] = mapInfo[j][i] = sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));
        }
    }
    //初始化到最小生成数的信息，假设从点 1 开始
    for (int i = 1; i <= n; i++)
        distanceToTree[i] = mapInfo[1][i];
    cnt = 1;//将点 1 放入树中
    while (cnt < n)
    {
        int temp_n;//局部变量用于存放即将连接的点
        double minDistance = 9999999;//局部变量用于存放到生成树的最小距离，即distanceToTree中的最小非零值
        for (int i = 1; i <= n; i++)
        {
            if (distanceToTree[i] != 0 && minDistance > distanceToTree[i])
            {
                minDistance = distanceToTree[i];
                temp_n = i;
            }
        }
        //将temp_n这个点放入树中
        cnt++;
        minSum += minDistance;//添加距离
        distanceToTree[temp_n] = 0;//由于temp_n已在树中，所以将它到树的距离置零，防止重复访问
        for (int i = 1; i <= n; i++)//将各个点到temp_n的距离，与各个点到树的距离进行比较（因为此时temp_n已经在树中），更新到树的距离
        {
            if (distanceToTree[i] > mapInfo[temp_n][i])
                distanceToTree[i] = mapInfo[temp_n][i];
        }
    }
    printf("%.2lf\n", minSum);
    return 0;
}

#include<stdio.h>
#include<algorithm>
#include<math.h>
#define N 101
using std::sort;
using std::sqrt;
int T[N];
int find(int x) {
    if (T[x] == -1)return x;
    else {
        int tmp = find(T[x]);
        T[x] = tmp;
        return tmp;
    }
}//寻找根节点
struct Edge {
    int a, b;
    double cost;
    bool operator<(const Edge &A)const {
        return cost < A.cost;
    }
}edge[500000];//边节点，重载<号
struct Point {
    double x, y;
    double distance(const Point &t)const {
        double tmp = (t.x - x)*(t.x - x) + (t.y - y)*(t.y - y);
        return sqrt(tmp);
    }
}point[1010];
int main() {
    int n;
    while (scanf("%d", &n) != EOF && n != 0) {
        for (int i = 1; i <= n; i++) T[i] = -1;//初始化树
        for (int i = 1; i <= n; i++) {
            scanf("%lf%lf", &point[i].x, &point[i].y);
        }//输入点
        int edgesize = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                edge[edgesize].a = i;
                edge[edgesize].b = j;
                edge[edgesize].cost = point[i].distance(point[j]);
                edgesize++;
            }
        }//输入边
        sort(edge, edge + edgesize);//对边排序
        double ans = 0;
        for (int i = 0; i <edgesize ; i++) {
            int a = find(edge[i].a);
            int b = find(edge[i].b);
            if (a != b) {
                ans += edge[i].cost;
                T[a] = b;
            }
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
/*并查集+KrusKal算法*/
struct Point
{
    double x;
    double y;
};
struct Edge
{
    //用编号代替点
    int from;
    int to;
    double length;
    bool operator<(const Edge&e)const{
        return length<e.length;
    }
};
const int MAXN=101;
Edge edge[MAXN*MAXN];//边集
Point point[MAXN];//点集
int father[MAXN];
int height[MAXN];
void InitialF(int n)//初始化
{
    for(int i=0;i<n;i++)
    {
        father[i]=i;
        height[i]=0;
    }
}
void Initial(int n)
{//构建边集，计算i到j的距离平方
    int count=0;
    for(int i=0;i<n;i++)
    {
        double length;
        for(int j=i+1;j<n;j++)
        {
            length=(point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y);
            edge[count].from=i;
            edge[count].to=j;
            edge[count++].length=length;
        }
    }
}
int Find(int x)//压缩路径
{
    if(x!=father[x])
        father[x]=Find(father[x]);
    return father[x];
}
void Union(int x,int y)//矮树挂高树
{
    x=Find(x);
    y=Find(y);
    if(x!=y)
    {
        if(height[x]>height[y])
            father[y]=x;
        else if(height[y]>height[x])
            father[x]=y;
        else{
            father[y]=x;
            height[x]++;
        }
    }
    return ;
}
double KrusKal(int n,int edgeNumber)
{
    InitialF(n);
    sort(edge, edge+edgeNumber);//从小到大排序
    double answer=0;
    for(int i=0;i<edgeNumber;i++)
    {
        if(Find(edge[i].from)!=Find(edge[i].to))
        {
            Union(edge[i].from, edge[i].to);
            answer+=sqrt(edge[i].length);
        }
    }
    return answer;
}
int main()
{
    int n;
    while(cin>>n)
    {
        int edgeNumber=n*(n-1)/2;
        for(int i=0;i<n;i++)
            cin>>point[i].x>>point[i].y;
        Initial(n);
        printf("%.2f\n",KrusKal(n, edgeNumber));
    }
    return 0;
}

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
struct point
{
	int index;
	double x, y;
	point(int i, double a, double b) :index(i), x(a), y(b) {}
};
struct edge
{
	int start, end;
	double dis;
	edge(int s, int e, double d) :start(s), end(e), dis(d) {}
};
double distance(point p1, point p2)
{	
	double a = abs(p1.x - p2.x);
	double b = abs(p1.y - p2.y);
	return sqrt(a * a + b * b);
}
int find_root(map<int, int>& V, int x)
{
	if (V.find(x) != V.end() && x != V[x])
		V[x] = find_root(V, V[x]);
	else
		return x;
	return V[x];
}
double kruskal(vector<edge>& E, int n)
{
	double cost = 0, count = 0;
	map<int, int> V;
	vector<edge>::iterator it = E.begin();
	while (count != n -1)
	{
		while (it != E.end())
		{
			int a = find_root(V,it->start);
			int b = find_root(V,it->end);
			if (a != b)
			{
				V[b] = a;
				cost += it->dis;
				it++;
				break;
			}
			else
				it++;
		}
		count++;
	}
	return cost;
}
bool comp(edge e1, edge e2)
{
	return e1.dis < e2.dis;
}
int main()
{
	int n;
	vector<point> P;
	vector<point>::iterator it;
	vector<edge> E;
	while (cin>>n)
	{
		for (int i = 0; i < n; i++)
		{
			double x, y;
			cin >> x >> y;
			point temp(i + 1, x, y);
			it = P.begin();
			while (it != P.end())
			{
				E.push_back(edge(it->index, temp.index, distance(*it, temp)));
				it++;
			}
			P.push_back(temp);
		}
		sort(E.begin(), E.end(), comp);
		cout.precision(2);
		cout<< fixed << kruskal(E, n) << endl;
		P.clear();
		E.clear();
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxv = 105;
typedef pair<double, double> pdd;
vector<pdd> point;
const double INF = 1100000000.0;
double getDis(pdd &a, pdd &b)
{
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
struct edge
{
    int to;
    double len;
    edge(int a, double b) : to(a), len(b) {}
};
struct node
{
    int v;
    double d;
    node(int a, double b) : v(a), d(b) {}
    bool operator < (const node &a) const
    {
        return d > a.d;
    }
};
vector<edge> g[maxv];
double dis[maxv];
bool vis[maxv];
priority_queue<node> q;
double Prim(int n)
{
    fill(dis, dis + n, INF);
    memset(vis, 0, sizeof(vis));
    dis[0] = 0;
    while(!q.empty())
        q.pop();
    q.push(node(0, dis[0]));
    double ans = 0;
    while(!q.empty())
    {
        int u = q.top().v;
        q.pop();
        if(vis[u])
            continue;
        vis[u] = 1;
        ans += dis[u];
        for(int i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i].to;
            double d = g[u][i].len;
            if(d < dis[v])
            {
                dis[v] = d;
                q.push(node(v, dis[v]));
            }
        }
    }
    return ans;
}
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        double x, y;
        point.clear();
        for(int i = 0; i < n; ++i)
        {
            scanf("%lf%lf", &x, &y);
            point.push_back(pdd(x, y));
        }
        for(int i = 0; i < n - 1; ++i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                double distance = getDis(point[i], point[j]);
                g[i].push_back(edge(j, distance));
                g[j].push_back(edge(i, distance));
            }
        }
        printf("%.2f\n", Prim(n));
    }
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS
(842)#include <iostream>
#include <cstdio>
(802)#include <algorithm>
#include <vector>
(721)#include <cmath>
using namespace std;
//Kruskal算法
const int MAXN = 110;
struct Point {
	float x,y;
}point[MAXN];

float getDistance(Point from, Point to);

struct Edge {
	int from;
	int to;
	float distance;
	Edge(int f, int t) :from(f), to(t), distance(getDistance(point[f], point[t])) {}
	bool operator<(Edge& e)const {
		return distance < e.distance;
	}
};
vector<Edge> edge;
int father[MAXN];
int height[MAXN];

float getDistance(Point from, Point to) {
	return sqrt(pow(from.x - to.x, 2) + pow(from.y - to.y, 2));
}

void Initial(int vexNum) {
	for (int i = 0; i <= vexNum; i++) {
		father[i] = i;
		height[i] = 0;
	}
}

int Find(int p) {
	if (father[p]!=p) {
		p = Find(father[p]);
	}
	return p;
}

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x != y) {
		if (height[x] < height[y]) {
			father[x] = y;
		}
		else if (height[x] > height[y]) {
			father[y] = x;
		}
		else {
			father[y] = x;
			height[x]++;
		}
	}
}

float Kruskal(int vexNum, int edgeNum) {
	Initial(vexNum);
	sort(edge.begin(), edge.end());
	float total = 0;
	for (int i = 0; i < edge.size(); i++) {
		Edge cur = edge[i];
		if (Find(cur.from) != Find(cur.to)) {
			total += cur.distance;
			Union(cur.from, cur.to);
		}
	}
	return total;
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		edge.clear();
		for (int i = 0; i < n; i++) {
			scanf("%f%f", &point[i].x, &point[i].y);
		}
		int edgeNum = n * (n - 1) / 2;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				edge.push_back(Edge(i, j));
			}
		}
		float total=Kruskal(n, edgeNum);
		printf("%.2f\n", total);
	}
	return 0;
}

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
struct edge
{
    int s;                //起点source
    int d;                //终点destination
    float dis;
}e[5000];               //100个点，最多只有(100*99)/2条边，大概5000条左右
int root[101];
int cmp(struct edge *a,struct edge *b)
{
    return (int)((a->dis)*100-(b->dis)*100);    //float型数据变量相减再转换回int会有误差，乘以100倍放大误差
}                                              //并且如果用 return a->dis>b->dis 会出错
int find(int x)
{
    int k=x,temp;
    while(x!=root[x])x=root[x];
    while(k!=root[k])                           //不用递归的路径压缩，大大降低树的高度
    {
        temp=root[k];
        root[k]=x;
        k=temp;
    }
    return x;
}
void join(int x,int y)
{
    int p=find(x),q=find(y);
    if(p!=q)root[q]=p;
}
float kruskal(int n,int nedge)                   //n为结点的个数，nedge为边条数
{
    qsort(e,nedge,sizeof(struct edge),cmp);        //排序
    float sum=0;
    int current=0;                          //已并入边数
    for(int i=0;i<n+1;i++)root[i]=i;       //初始化root数组
    for(int i=0;i<nedge;i++)
    {
        int a=e[i].s,b=e[i].d;
        if(find(a)!=find(b))
        {
            join(a,b);
            sum+=e[i].dis;
            current++;
        }
        if(current==n-1)break;       //如果已经有n-1条边，就不继续了，最小生成树边数比结点数少1
    }
    return sum;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        float xy[n][2];
        int p=0;
        for(int i=0;i<n;i++)scanf("%f%f",&xy[i][0],&xy[i][1]);
        for(int i=0;i<n;i++)               //两两相连
        {
            for(int j=i+1;j<n;j++)
            {
                e[p].s=i;
                e[p].d=j;
                e[p++].dis=sqrt((xy[i][0]-xy[j][0])*(xy[i][0]-xy[j][0])+(xy[i][1]-xy[j][1])*(xy[i][1]-xy[j][1]));
            }
        }
        printf("%.2f\n",kruskal(n,(n*(n-1))/2));      //边数为n*(n-1)/2
    }
}

最小生成树的模板题，开始看成了旅行商浪费好长时间。。。

#include<cmath>
#define N 100
#define INF 1000000
using namespace std;

int n;
double dis[N][N];
double d[N];
bool vis[N];

struct point{
    double x, y;
}points[100];

double distant(point a, point b){
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

void init(int n){
    for(int i = 0; i < n; i++){
        cin >> points[i].x >> points[i].y;
    }

    double d;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            d = distant(points[i], points[j]);
            dis[i][j] = d;
            dis[j][i] = d;
        }
    }
}

double prim(){
    fill(vis, vis + N, false);
    fill(d, d + N, INF);
    d[0] = 0;
    double ret = 0;
    for(int i = 0; i < n; i++){
        int u = -1;
        double MIN = INF;
        for(int j = 0; j < n; j++){
            if(vis[j] == false && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1)    return -1;
        vis[u] = true;
        ret += d[u];
        for(int v = 0; v < n; v++){
            if(vis[v] == false && dis[u][v] != INF && dis[u][v] < d[v]){
                d[v] = dis[u][v];
            }
        }
    }
    return ret;
}

int main(){
    double ret;
    while(cin >> n){
        init(n);
        ret = prim();
        printf("%.2f\n", ret);
    }
    return 0;
}

#include <iostream>
#include <limits.h>
#include <cmath>
using namespace std;
#define N 105
inline double getDist(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
void prim(int n, double c[N][N]){
    double sum = 0;
    double *lowcost = new double[n];
    int *closest = new int[n];
    bool *s = new bool[n];
    s[0] = true;
    for (int i = 1; i < n; i++){
        lowcost[i] = c[0][i];
        closest[i] = 0;
        s[i] = false;
    }
    for (int i = 1; i<n; i++){
        double min = INT_MAX;
        int j = 0;
        for (int k = 1; k <n; k++){
            if (lowcost[k]<min && (!s[k])){
                min = lowcost[k];
                j = k;
            }
        }
        sum += c[j][closest[j]];
        s[j] = true;
        for (int k = 1; k < n; k++){
            if ((c[j][k]<lowcost[k]) && (!s[k])){
                lowcost[k] = c[j][k];
                closest[k] = j;
            }
        }
    }
    cout << sum << endl;
}
int main(){
    int n;
    double c[N][N] = {{0}}, coord[N][2];
    while (cin >> n){
        for (int i = 0; i<n; i++){
            cin >> coord[i][0] >> coord[i][1];
        }
        for (int i = 0; i<n; i++){
            for (int j = 0; j<n; j++){
                c[i][j] = getDist(coord[i][0], coord[i][1], coord[j][0], coord[j][1]);
            }
        }
        prim(n, c);
    }
}

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define N 101
int Tree[N];
using namespace std;
int FindRoot(int x){
    if(Tree[x]==-1) return x;
    else{
        Tree[x]=FindRoot(Tree[x]);
        return Tree[x];
    }
}
typedef struct Edge{
    int a,b;
    double distance;
}Edge;
typedef struct Point{
    double x,y;
}Point;
int cmp(Edge a,Edge b){
    return a.distance<b.distance;
}
double getdis(Point a,Point b){
    return sqrt(pow(b.y-a.y,2)+pow(b.x-a.x,2));
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        Point p[N];
        Edge e[N*(N-1)/2];
        int i;
        for(i=1;i<=n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        int size=0;
        for(i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++){
                e[size].a=i;
                e[size].b=j;
                e[size++].distance=getdis(p[i],p[j]);
            }
        sort(e,e+size,cmp);
        for(i=1;i<=n;i++)
            Tree[i]=-1;
        int a,b;
        double d=0;
        for(i=0;i<size;i++){
            a=FindRoot(e[i].a);
            b=FindRoot(e[i].b);
            if(a!=b){
                Tree[b]=a;
                d+=e[i].distance;
            }
        }
        printf("%.2lf\n",d); 
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
/**
 * 首先利用kruskcal算法实现,
 * 算法实现的关键是并查集的实现
*/
struct point{
    double x;
    double y;
    point(double a=0,double b=0):x(a),y(b){}
}v[105];
struct edge{
    int a,b;
    double len;
    edge(int x=0,int y=0,double l=0):a(x),b(y),len(l){}
    bool operator< (const edge & e)const{
        return this->len<e.len;
    }
}e[10000];

int n;
int parent[105];
/**
 * 并查集实现
*/
void UFset(){//并查集初始化
    for(int i=0;i<n;i++)
        parent[i]=-1;

}
int UFfind(int x){
    //找到x节点所在树的根节点
    int ret;
    for(ret=x;parent[ret]>=0;ret=parent[ret]);
    //优化方案 --压缩路径，方便后续查找
    while(ret!=x){
        int tmp=parent[x];
        parent[x]=ret;
        x=tmp;
    }
    return ret;
}
void UFunion(int R1,int R2){
    //合并R1 ，R2所在树
    int root1=UFfind(R1);
    int root2=UFfind(R2);
    //parent[root1 root2]都是小于零的数
    if(parent[root1]>parent[root2]){
        parent[root2]+=parent[root1];
        parent[root1]=root2;

    }
    else {
        parent[root1]+=parent[root2];
        parent[root2]=root1;
    }
}
int main(){
    while(cin>>n&&n){
        for(int i=0;i<n;i++){
            double x,y;
            cin>>x>>y;
            v[i]=point(x,y);
        }
        UFset();

        // 构建边集合
        int k=0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                double len=sqrt(pow(v[i].x-v[j].x,2)+pow(v[i].y-v[j].y,2));
                e[k++]=edge(i,j,len);
            }
        }
        double sum=0;
        //按边从小到大排序
        sort(e,e+k);
        for(int i=0;i<k;i++){
            int a=e[i].a;
            int b=e[i].b;
            int r1=UFfind(a);
            int r2=UFfind(b);
            if(r1!=r2){
                sum+=e[i].len;
                UFunion(r1,r2);
            }
        }
        printf("%.2f\n",sum);




    }
    return 0;
}

	

#include<iostream>
#include<iomanip>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
struct node{
    int num;
    double x;
    double y;
};
struct res{
    double dis;
    int node1;
    int node2;
    res(double _dis,int _node1,int _node2){
        dis=_dis;
        node1=_node1;
        node2=_node2;
    }
};
int visit[110];
bool compare(res lhs,res rhs){
    if(lhs.dis<rhs.dis){
        return true;
    }
    else return false;
}
void Initset(int n){
    for(int i=0;i<n;i++){
        visit[i]=i;
    }
}
int findfather(int n){
    if(visit[n]==n){
        return n;
    }
    else return findfather(visit[n]);
}
int main(){
    int n;
    cin>>n;
    vector<node>coordi(n);
    vector<res>dis;
    Initset(n+1);
    for(int i=0;i<n;i++){
        cin>>coordi[i].x>>coordi[i].y;
        coordi[i].num=i+1;
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            double distance=sqrt(pow(fabs(coordi[i].x-coordi[j].x),2)+pow(fabs(coordi[i].y-coordi[j].y),2));
            int s=coordi[i].num;
            int t=coordi[j].num;
            res resnode(distance,s,t);
            dis.push_back(resnode);
        }
    }
    sort(dis.begin(),dis.end(),compare);
    double sum=0;
    int setnode=n;
    for(vector<res>::iterator it=dis.begin();it!=dis.end();it++){
        int a=(*it).node1;
        int b=(*it).node2;
        int aroot=findfather(a);
        int broot=findfather(b);
        if(aroot!=broot){
            visit[broot]=aroot;
            sum+=(*it).dis;
            setnode--;
        }
        if(setnode==1){
            break;
        }
    }
    cout<<fixed<<setprecision(2)<<sum<<endl;
    return 0;
}