解题思路

本题可以抽象为最小生成树（Minimum Spanning Tree, MST）问题：

1. 建模：将每个雀斑看作图中的顶点，顶点之间的边的权值为两点之间的欧几里得距离。
2. 算法选择：使用 Prim算法 或Kruskal算法 求解最小生成树。
3. 输出结果：最小生成树中所有边的权值之和即为所需的最小墨水总量。

关键公式

• 两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的距离 $d$：$$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

解决代码

#include "bits/stdc++.h"

using namespace std;

//最大点数 
const int MAXV = 110;

//最大边数 
const int MAXE =  (100*99) / 2 + 10; 

const int INF = 0x3fffffff;

struct edge{
	int u;
	int v;
	double cost;
}E[MAXE]; 

int len = 0;	//边数组的大小 

//点坐标数组 
double point[MAXV][2];

//输入的点的数 
int n;

//并查集father数组
int father[MAXV]; 

//距离计算函数 
double distance(double x1,double x2,double y1,double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

bool cmp(edge a,edge b){
	return a.cost < b.cost;
}

int findFather(int x){
	if(father[x] == x){
		return x;
	}
	//持续更新自身的father 
	int root = findFather(father[x]);
	father[x] = root;
	return root;
} 

double kruskal(){
	//最小生成树长度 
	double ans = 0;
	
	//记录有多少条边加入到最小生成树中 
	int cnt = 0; 
	
	//对边进行排序 
	sort(E,E+len,cmp);
	
	//遍历E数组中的所有边，边的总数是len 
	for(int i=0;i<len;i++){
		int u = E[i].u;
		int v = E[i].v;
		double cost = E[i].cost;
		
		//找到双方的并查集的根结点 
		int fatherU = findFather(u);
		int fatherV = findFather(v);
		
		//如果在一个并查集中
		if(fatherU == fatherV){
			continue;	//是continue，不是break 
		}else{	//不在一个并查集中，合并 
			father[fatherU] = fatherV;
			ans += cost; 
			cnt++; 
			//为了早日跳出循环，我们加入下面的判断
			if(cnt == n-1){
				break;
			}
		}	
	}
	
	//为不连通的图 
	if(cnt != n-1){
		return -1;
	}
	
	return ans; 
}

int main(){
	while(~scanf("%d",&n)){
		//公共数据结构的初始化
		fill(point[0],point[0]+MAXV*2,INF);
		
		double x,y;
		
		for(int i=0;i<n;i++){
			scanf("%lf %lf",&x,&y);
			point[i][0] = x;
			point[i][1] = y;
			
			//初始化father都是自己 
			father[i] = i;	
		}
		
		//计算两点之间的边，一共应该有(n*(n-1))/2条边
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				double cost = distance(point[i][0],point[j][0],point[i][1],point[j][1]);
				edge tmp;
				tmp.u = i;
				tmp.v = j;
				tmp.cost = cost;
				E[len++] = tmp; 
			}
		}
		
		double ans = 0;
		
		//开始进行kruskal算法
		ans = kruskal(); 
		
		//结果保留两位小数 
		printf("%.2f\n",ans);
	}
	return 0;
}