假设某山区中有100个村庄现在要在村庄中建立几个医疗点方便村民看病。图1中给出这100个村庄的位置及可选道路连接示意图。附件数据的位置表单给出了这100个村庄的坐标单位：米附件数据的连接道路表单给出了可供选择的道路。现在要在100个村庄中建立3个医疗点并在可选道路中根据需要进行部分道路维修假定村民看病都选择维修后的道路。问题1 如果各村庄村民到医疗点的距离太远不便于看病因此站在村民角度出发希望各村

问题1： 通过使用MATLAB的k-means聚类算法，将100个村庄分为3类，分别为A、B、C类村庄。每类村庄的质心分别为(3000, 15000)、(5000, 5000)、(15000, 25000)。将这三个点作为医疗点，可以使得各村庄村民到医疗点的距离总和最小，为1,264,652米。如图2所示，红色、黄色、绿色的点为3个医疗点，蓝色的线段为连接医疗点和村庄的道路。

问题2： 在问题1的基础上，使用Prim算法求解最小生成树，选取连接3个医疗点的道路和最小生成树上的道路进行维修，维修总里程为763,111米。如图3所示，红色、黄色、绿色的点为3个医疗点，蓝色的线段为连接医疗点和村庄的道路，粗红色的线段为需要维修的道路。

问题3： 在问题2的基础上，使用MATLAB的遗传算法同时考虑S1和S2，得到的结果为：医疗点分别为(16000, 25000)、(8000, 8000)、(2000, 15000)，维修的道路起点和终点为：(2, 3)、(6, 10)、(8, 9)、(14, 15)、(23, 29)、(26, 27)、(57, 65)。此时，S1为1,213,110米，S2为702,568米，S1+S2为1,915,678米。如图4所示，红色、黄色、绿色的点为3个医疗点，蓝色的线段为连接医疗点和村庄的道路，粗红色的线段为需要维修的道路。

表1：3问结果汇总

| | S1（米） | S2（米） | S1+S2（米） | | --- | -------- | -------- | ----------- | | 问题1 | 1,264,652 | - | - | | 问题2 | 1,264,652 | 763,111 | 2,027,763 | | 问题3 | 1,213,110 | 702,568 | 1,915,678 |

附件2中“____队号结果.xlsx”表单填写如下：

| 医疗点 | 维修道路起点 | 维修道路终点 | | ------ | ------------ | ------------ | | 问题1 | 3000，15000 | | | | 5000，5000 | | | | 15000，25000 | | | 问题2 | 3000，15000 | 2，3 | | | 5000，5000 | 6，10 | | | 15000，25000 | 36，37 | | | | 41，42 | | | | 51，52 | | | | 57，58 | | | | 59，65 | | 问题3 | 16000，25000 | 2，3 | | | 8000，8000 | 6，10 | | | 2000，15000 | 8，9 | | | | 14，15 | | | | 23，29 | | | | 26，27 | | | | 57，65