[编程题]Freckles
- 热度指数：8467 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through.
Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.
输入描述:
The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.
输出描述:
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.
示例1
输入
3 1.0 1.0 2.0 2.0 2.0 4.0
输出
3.41
#include<iostream>
(720)#include<sstream>
#include<algorithm>
(831)#include<queue>
#include<cmath>
(808)#include<string>
#include<cstdio>
(802)#include<regex>
#include<vector>
(721)#include<stack>
#include<bitset>
(1494)#include<iomanip>
#include<stdlib.h>
(794)#include<map>
using namespace std;
const int N = 200;
struct Edge
{
int start;
int end;
double length;
//int builded;
bool operator < (Edge c) const
{
return length < c.length;
}
};
struct point
{
double x;
double y;
};
int father[N];
int height[N];
void Initial()
{
for (int i = 0; i < N; i++)
{
father[i] = i;
height[i] = 0;
}
}
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[x] < height[y])
father[x] = y;
else
{
father[y] = x;
height[x]++; //二者高度相同时，其中一个加1
}
}
}
double Kruskal(vector<Edge>edge)
{
double count = 0;
sort(edge.begin(), edge.end());
//sort(unedge.begin(), unedge.end());
for (int i = 0; i < edge.size(); i++)
{
if (Find(edge[i].start) != Find(edge[i].end))
{
Union(edge[i].start, edge[i].end);
count = count+edge[i].length;
}
}
/*for (int i = 0; i < unedge.size(); i++)
{
if (Find(unedge[i].start) != Find(unedge[i].end))
{
Union(unedge[i].start, unedge[i].end);
count += unedge[i].length;
}
}
*/
return count;
}
double distance(double x1, double y1, double x2,double y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
int main()
{
int n;
while (cin >> n)
{
Initial();
vector<point> points;
vector<Edge> edges;
for (int i = 0; i < n; i++)
{
point a;
cin >> a.x >> a.y;
points.push_back(a);
}
for(int i=0;i<points.size();i++)
for (int j = i + 1; j<points.size()&&j > i; j++)
{
Edge s;
s.start = i;
s.end = j;
s.length = distance(points[i].x, points[i].y, points[j].x, points[j].y);
edges.push_back(s);
}
cout <<fixed<<setprecision(2)<< Kruskal(edges) << endl;
}
}
发表于 2020-03-11 16:38:22
回复(0)
#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;
}
本算法采用的是prim算法：即每次都将到生成树的最小距离的点放入树中，直到所有的点都已被访问或者访问了n - 1条边。
到生成树的最小距离：使用一个一维数组进行模拟
初始情况是将1放放进树中，然后定义一个一维数组，用于存放到生成树的距离，由于1在树中，所以此刻到树中的距离是到1的距离，然后找出这个一维数组中的最小值，把这个最小值对应的点 temp放入树中，此刻由于2也在树中，（需要将2到树中的距离置零）所以要更新到树中的距离，（将各个点到temp的距离，与各个点到生成树的距离进行比较），直到访问了所有的点
发表于 2018-09-23 15:48:51
回复(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;
}
发表于 2018-06-05 19:21:37
回复(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;
}
发表于 2018-03-07 15:06:31
回复(1)
#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;
}
发表于 2022-03-31 11:06:36
回复(0)
学会了用set存自己写的类
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
class Dot {
public:
double x{};
double y{};
double getDistance(Dot other) {
return sqrt(pow(x - other.x, 2) + pow(y - other.y, 2));
}
Dot(double x, double y) :x(x), y(y) {};
Dot() = default;
bool operator < (const Dot& p) const {
if (this->x < p.x) {
return true;
}
else if (this->x > p.x) {
return false;
}
else if (this->y < p.y) {
return true;
}
else {
return false;
}
}
};
void prim(set<Dot> U, set<Dot> V) {
double sum = 0;
Dot tmp;
while (!V.empty()) {
double mmin = 0xffff;
for (auto u : U) {
for (auto v : V) {
double distance = u.getDistance(v);
if (distance < mmin) {
mmin = min(mmin, distance);
tmp = v;
}
}
}
U.insert(tmp);
V.erase(tmp);
sum += mmin;
}
printf("%.2lf\n", sum);
}
int main() {
int n;
while (cin >> n) {
double x, y;
set<Dot> U, V;
cin >> x >> y;
U.insert(Dot(x, y));
for (int i = 1; i <= n - 1; i++) {
cin >> x >> y;
V.insert(Dot(x, y));
}
prim(U, V);
}
return 0;
}
发表于 2021-03-15 13:09:26
回复(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;
} 写的有点麻烦，但应该挺清晰
编辑于 2020-07-01 16:56:47
回复(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;
}
基本属于裸的最小生成树，为了增加难度用带堆优化的Prim实现了一遍
发表于 2020-05-20 13:57:10
回复(0)
为了压行而生🤣 破圈法即可
#include<iostream>
(720)#include<string>
#include<string.h>
(845)#include<vector>
#include<algorithm>
(831)#include<queue>
#include<cstdio>
(802)#include<set>
using namespace std;
#define MAX 105
(5434)#define ll int
#define inf 100000000
(5431)#define vec vector<ll>
struct P {
double x, y;
}points[MAX];
struct edge {
ll from, to; double dist;
edge(ll f = 0, ll t = 0, double d = 0) { from = f, to = t, dist = d; }
};
bool cmp(edge e1, edge e2) { return e1.dist < e2.dist; }
double d(P p1, P p2) {
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
ll n, kind[MAX], cnt; double a, b, res = 0;
ll find(ll k) {
if (kind[k] == k)return k;
else return kind[k] = find(kind[k]);
}
void unite(ll a, ll b) { kind[find(b)] = kind[find(a)]; }
int main() {
while (cin >> n) {
vector<edge> v; res = 0; cnt = 0;
for (int i = 0; i < n; i++)kind[i] = i;
for (int i = 0; i < n; i++)
cin >> points[i].x >> points[i].y;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double dis = d(points[i], points[j]);
v.push_back(edge(i, j, dis));
}
}
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < v.size() && cnt < n - 1; i++) {
edge e = v[i];
if (find(e.from) == find(e.to))continue;
unite(e.from, e.to); res += e.dist; cnt++;
}
printf("%.2f", res);
}
}
发表于 2020-04-21 09:45:43
回复(0)
Pime算法。
#include<cstdio>
(802)#include<vector>
#include<cmath>
using namespace std;
const int maxn = 105;
const double inf = 0x7fffffff;
double d[maxn];
int n;
bool vis[maxn];
struct Point {
double x, y;
int id;
};
vector<Point> pv;
double g[maxn][maxn];
double prim(int st) {
fill(d, d + maxn, inf);
d[st] = 0;
double ans = 0;
for (int i = 0; i < n; ++i) {
double minD = inf;
int u = -1;
for (int v = 0; v < n; ++v) {
if (!vis[v] && d[v] < minD) {
minD = d[v];
u = v;
}
}
if (u == -1) {
return -1;
} else {
vis[u] = true;
ans += d[u];
for (int v = 0; v < n; ++v) {
if (!vis[v] && g[u][v] != inf && g[u][v] < d[v]) {
d[v] = g[u][v];
}
}
}
}
return ans;
}
double getDist(Point a, Point b) {
double tmp = pow(a.x - b.x, 2) + pow(a.y - b.y, 2);
return sqrt(tmp);
}
int main() {
scanf("%d", &n);
double x, y;
for (int i = 0; i < n; ++i) {
scanf("%lf %lf", &x, &y);
pv.push_back(Point{x, y, i});
}
for (int i = 0; i < pv.size(); ++i) {
for (int j = i; j < pv.size(); ++j) {
int a = pv[i].id;
int b = pv[j].id;
if (a == b) {
g[a][b] = inf;
} else {
g[b][a] = g[a][b] = getDist(pv[i], pv[j]);
}
}
}
double ans = prim(0);
printf("%.2lf", ans);
return 0;
}
发表于 2020-04-07 16:30:35
回复(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;
}
发表于 2020-03-22 17:56:38
回复(0)
/*很显然是最小生成树的问题，因为给的是每个点的坐标，所以可以计算每两个点之间的距离，这样用矩阵保存图就很方便。用普利姆或者克鲁斯卡尔很容易能算出最小生成树，这里因为计算边会比较麻烦，所以直接用了prim
*/
# include<stdio.h>
#include<algorithm>
# include<math.h>
using namespace std;
const int maxn=110;
const double INF=1000000;
double result=0;
double A[maxn][maxn];
double d[maxn];
bool visit[maxn]= {false};
int n;
struct point { //用来保存每个点的x,y ,以便于计算各点之间的距离
double x;
double y;
} p[110];
#include<algorithm>
# include<math.h>
using namespace std;
const int maxn=110;
const double INF=1000000;
double result=0;
double A[maxn][maxn];
double d[maxn];
bool visit[maxn]= {false};
int n;
struct point { //用来保存每个点的x,y ,以便于计算各点之间的距离
double x;
double y;
} p[110];
double dis (point a,point b) { //计算 ab之间的距离
double d;
d=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return d;
}
void prim() { //普利姆算法
int i,j,v;
fill(d,d+maxn,INF);
d[0]=0;
for(i=0; i<n; i++) {
int u=-1;
double min=INF;
for(j=0; j<n; j++) {
if(d[j]<min&&visit[j]==false) {
u=j;
min=d[j];
}
}
if(u==-1)
return ;
visit[u]=true;
result+=d[u];
for(v=0; v<n; v++) {
if(d[v]>A[u][v]&&visit[v]==false) {
d[v]=A[u][v];
}
}
}
}
int main () {
int i,j;
double x,y;
while(scanf("%d",&n)!=EOF) {
for(i=0;i<n;i++){
scanf("%lf%lf",&x,&y);
p[i].x=x;
p[i].y=y;
}
for(i=0; i<n; i++) { //将图保存在矩阵中，以便于用prim 计算最小生成树
for(j=0; j<n; j++) {
A[i][j]=dis(p[i],p[j]);
}
}
prim();
printf("%.2f",result);
}
return 0;
}
double d;
d=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return d;
}
void prim() { //普利姆算法
int i,j,v;
fill(d,d+maxn,INF);
d[0]=0;
for(i=0; i<n; i++) {
int u=-1;
double min=INF;
for(j=0; j<n; j++) {
if(d[j]<min&&visit[j]==false) {
u=j;
min=d[j];
}
}
if(u==-1)
return ;
visit[u]=true;
result+=d[u];
for(v=0; v<n; v++) {
if(d[v]>A[u][v]&&visit[v]==false) {
d[v]=A[u][v];
}
}
}
}
int main () {
int i,j;
double x,y;
while(scanf("%d",&n)!=EOF) {
for(i=0;i<n;i++){
scanf("%lf%lf",&x,&y);
p[i].x=x;
p[i].y=y;
}
for(i=0; i<n; i++) { //将图保存在矩阵中，以便于用prim 计算最小生成树
for(j=0; j<n; j++) {
A[i][j]=dis(p[i],p[j]);
}
}
prim();
printf("%.2f",result);
}
return 0;
}
发表于 2020-03-18 17:48:12
回复(0)
将点两两相连，然后用kruskral算法。
#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
}
}
编辑于 2020-03-10 18:55:47
回复(0)
//求最小生成树
#include <stdio.h>
#include <algorithm>
#include<math.h>
using namespace std;
int Tree[100];
struct Node{
double x;
double y;
int index; //本结点下标
}p[100];
struct Edge{
Node head;
Node tail;
double length;
}e[10000];
int findRoot(int x){
if(Tree[x]==-1) return x;
else{
int r=findRoot(Tree[x]);
Tree[x]=r;
return r;
}
}
double edgelength(Node a,Node b){
double ans;
ans=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return ans;
}
bool cmp(Edge a,Edge b){
return a.length<b.length;
}
bool mark[10000];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
int num=0; //边数
for(int i=1;i<=n;i++){
scanf("%lf",&p[i].x);
scanf("%lf",&p[i].y);
Tree[i]=-1;
p[i].index=i;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
e[num].head=p[i];
e[num].tail=p[j];
e[num].length=edgelength(p[i],p[j]);
num++;
}
}
for(int i=0;i<num;i++) mark[i]=false; //false表示边已使用
sort(e,e+num,cmp); //对边按长度从小到大排序
double sum=0;
for(int i=1;i<n;i++){ //n个结点的生成树只有n-1条边
for(int j=0;j<num;j++){ //
if(mark[j]==true) continue;
Node na=e[j].head;
Node nb=e[j].tail;
int a=na.index;
int b=nb.index;
a=findRoot(a);
b=findRoot(b);
if(a!=b){
sum+=e[j].length;
Tree[a]=b;
}
mark[j]=true;
}
}
printf("%.2f\n",sum);
}
}
#include <stdio.h>
#include <algorithm>
#include<math.h>
using namespace std;
int Tree[100];
struct Node{
double x;
double y;
int index; //本结点下标
}p[100];
struct Edge{
Node head;
Node tail;
double length;
}e[10000];
int findRoot(int x){
if(Tree[x]==-1) return x;
else{
int r=findRoot(Tree[x]);
Tree[x]=r;
return r;
}
}
double edgelength(Node a,Node b){
double ans;
ans=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return ans;
}
bool cmp(Edge a,Edge b){
return a.length<b.length;
}
bool mark[10000];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
int num=0; //边数
for(int i=1;i<=n;i++){
scanf("%lf",&p[i].x);
scanf("%lf",&p[i].y);
Tree[i]=-1;
p[i].index=i;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
e[num].head=p[i];
e[num].tail=p[j];
e[num].length=edgelength(p[i],p[j]);
num++;
}
}
for(int i=0;i<num;i++) mark[i]=false; //false表示边已使用
sort(e,e+num,cmp); //对边按长度从小到大排序
double sum=0;
for(int i=1;i<n;i++){ //n个结点的生成树只有n-1条边
for(int j=0;j<num;j++){ //
if(mark[j]==true) continue;
Node na=e[j].head;
Node nb=e[j].tail;
int a=na.index;
int b=nb.index;
a=findRoot(a);
b=findRoot(b);
if(a!=b){
sum+=e[j].length;
Tree[a]=b;
}
mark[j]=true;
}
}
printf("%.2f\n",sum);
}
}
发表于 2019-03-09 22:02:32
回复(0)
最小生成树的模板题，开始看成了旅行商浪费好长时间。。。
#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;
}
发表于 2019-03-08 16:41:12
回复(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);
}
}
编辑于 2018-09-15 00:29:50
回复(0)
#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;
}
发表于 2018-01-20 22:23:48
回复(2)
Prim算法求最小生成树 C++
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
//顶点结构体
using dot = struct dot {
float x;
float y;
};
//边类
class line {
public:
int start;
int end;
float length;
line(int s, int e, float l): start(s), end(e), length(l) {}
bool static compare(line a, line b) {
return (a.length < b.length);
}
};
int main() {
int n;
while (cin >> n) {
vector<dot> dots(n);
for (int i = 0; i < n; i++)
cin >> dots[i].x >> dots[i].y;
//计算所有可能的边的长度
vector<line> lines;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
float dx = dots[i].x - dots[j].x;
float dy = dots[i].y - dots[j].y;
float length = sqrt(dx * dx + dy * dy);
lines.emplace_back(i, j, length);
}
}
//按边长升序排序
sort(lines.begin(), lines.end(), line::compare);
//Prim算法求最小生成树
set<int> s; //已加入树的点的集合
s.insert(0); //初始树只有0号点
float sum = 0;
//循环直到所有顶点都加入树中
while (s.size() < dots.size()) {
//寻找长度最小且连接树内和树外的边
for (int i = 0; i < lines.size(); i++) {
if (s.find(lines[i].start) != s.end() && s.find(lines[i].end) == s.end()) {
s.insert(lines[i].end);
sum += lines[i].length;
break;
} else if (s.find(lines[i].end) != s.end() &&
s.find(lines[i].start) == s.end()) {
s.insert(lines[i].start);
sum += lines[i].length;
break;
}
}
}
cout.setf(ios::fixed);
cout.precision(2);
cout << sum;
}
}
发表于 2023-02-11 02:21:03
回复(0)
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int father[100];
int height[100];
void Initial() {
for (int i = 0; i < 100; i++) {
father[i] = i;
height[i] = 0;
}
}
//并查集的查找操作
int find(int x) {
if (x != father[x]) {
father[x] = find(father[x]);
}
return father[x];
}
//并查集的合并操作
bool 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[x] < height[y]) {
father[x] = y;
} else {
father[y] = x;
height[x]++;
}
return true;
}
return false;
}
//点的数据封装
struct point {
double x;
double y;
point(double x, double y): x(x), y(y) {}
};
//边的数据封装
struct edge {
int from;
int to;
double weight;
edge(int from, int to, double weight): from(from), to(to), weight(weight) {}
bool operator< (const edge& e)const {
return this->weight < e.weight;
}
};
int main() {
int n;
while (cin >> n) {
Initial();
vector<point> points;
double x, y;
//将 点坐标 都储存起来
int t = n;
while (t--) {
cin >> x >> y;
point p(x, y);
points.push_back(p);
}
vector<edge> es;
//计算出每个点之间的距离作为边的权值 并将边存储起来
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double weight = sqrt(pow(points[i].x - points[j].x,
2.0) + pow(points[i].y - points[j].y, 2.0));
edge e(i, j, weight);
es.push_back(e);
}
}
//克鲁斯卡尔算法
double ans = 0;
sort(es.begin(), es.end());
for (int i = 0; i < es.size(); i++) {
if (Union(es[i].from, es[i].to)) {
ans += es[i].weight;
}
}
printf("%.2f", ans);
}
return 0;
}
编辑于 2024-03-05 19:49:31
回复(0)
/*
题目翻译：
描述:
在Dick Van Dyke节目的一集中，
小Richie（里奇）把他爸爸背上的雀斑连接起来，
形成了一张自由钟的照片。
唉，其中一个雀斑原来是一道疤痕，
所以他的雷普利订婚失败了。
把迪克的背部想象成一个平面，在不同的（x，y）位置都有雀斑。
你的工作是告诉里奇如何连接这些点，从而最大限度地减少墨水的使用量。
里奇通过在两对之间画直线来连接这些点，可能会在两行之间提笔。
当Richie完成时，必须有一系列从任何雀斑到任何其他雀斑的连线。
输入描述：
第一行包含0＜n＜＝100，即迪克背上雀斑的数量。
每一个雀斑都有一条线；下面的每一行都包含两个实数，表示雀斑的（x，y）坐标。
输出描述：
您的程序打印一个实数到小数点后两位：可以连接所有雀斑的墨水线的最小总长度。
*/
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 101;
struct Point {
double x, y; //点的坐标
};
struct Edge {
int from; //边的起点
int to; //边的终点
double length; //边的长度
Edge(int f, int t, double l): from(f), to(t), length(l) {} //构造函数
bool operator<(const Edge& e)const { //重载小于号
return length < e.length;
}
};
vector<Point>point(MAXN); //点集
vector<Edge>edge; //边集
vector<int>father(MAXN); //父亲结点
vector<int>height(MAXN); //结点高度
void Initial(int n) { //初始化
for (int i = 0; i <= n; i++) {
father[i] = i;
height[i] = 0;
}
}
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[x] = y;
} else if (height[y] < height[x]) {
father[y] = x;
} else {
father[y] = x;
height[x]++;
}
}
}
//克鲁斯卡尔算法求最小生成树，返回最小总长度
double Kruskal(int n, int edgeNum) {
Initial(n);
sort(edge.begin(), edge.begin() + edgeNum); //按权值排序
double sum = 0;
for (int i = 0; i < edgeNum; i++) {
Edge current = edge[i];
if (Find(current.from) != Find(current.to)) {
Union(current.from, current.to);
sum += current.length;
}
}
return sum;
}
int main() {
int n;
while (cin >> n) {
for (int i = 0; i < n; i++) {
cin >> point[i].x >> point[i].y; //输入各点坐标
}
//构造边集
int edgeNum = n * (n - 1) / 2;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) { //遍历各点
double x = point[i].x - point[j].x;
double y = point[i].y - point[j].y;
double length = sqrt(x * x + y * y);
edge.emplace_back(i, j, length);
}
}
cout << Kruskal(n, edgeNum) << endl;
}
return 0;
}
编辑于 2024-02-21 14:53:09
回复(0)
问题信息
难度：
79条回答
109收藏
8063浏览
通过挑战的用户
查看代码-
2023-03-04 13:03:56
-
2023-03-01 10:18:55 -
2023-02-25 16:59:59
-
2023-02-12 19:13:41 -
2023-02-05 16:37:14
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
