用python代码的贪心算法解决：在100个村庄中建立3个医疗点，并在可选道路中根据需要进行部分道路维修，假定村民看病都选择维修后的道路。如果要使各村庄村民到医疗点的距离总和S1最小，请问这3个医疗点分别建立在何处最好？总距离S1是多少？ 各村庄村民都选择最近的医疗点看病，请问应该维修哪些道路，维修道路总里程S2是多少？

首先，我们可以使用贪心算法来解决第一个问题。按照以下步骤进行：

1. 随机选择3个村庄作为医疗点的位置。
2. 对于每个村庄，将其与离它最近的医疗点连接起来。
3. 计算所有村庄到最近的医疗点的距离，并将其相加得到S1。
4. 对于每个村庄，计算与未连接的医疗点之间的距离，并选择其中最小的距离作为该村庄连接的道路。
5. 对于每个连接的道路，计算其长度并将其相加得到S2。

以下是Python代码实现：

import random
import sys

# 定义村庄和医疗点数量
village_num = 100
clinic_num = 3

# 定义村庄和医疗点的坐标范围
x_range = [0, 1000]
y_range = [0, 1000]

# 定义道路的修建和未修建的代号
UNBUILT = 0
BUILT = 1

# 计算两点之间的距离
def distance(p1, p2):
    return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

# 随机生成村庄和医疗点的坐标
villages = [(random.uniform(x_range[0], x_range[1]), random.uniform(y_range[0], y_range[1])) for _ in range(village_num)]
clinics = [(random.uniform(x_range[0], x_range[1]), random.uniform(y_range[0], y_range[1])) for _ in range(clinic_num)]

# 初始化距离矩阵
distances = [[distance(village, clinic) for clinic in clinics] for village in villages]

# 记录每个村庄连接到的最近医疗点的下标
village_to_clinic = [-1] * village_num

# 记录每条道路的修建状态和长度
roads = [[UNBUILT] * village_num for _ in range(village_num)]
road_lengths = [[0] * village_num for _ in range(village_num)]

# 将每个村庄连接到离它最近的医疗点
for i, village in enumerate(villages):
    nearest_clinic = min(range(clinic_num), key=lambda j: distances[i][j])
    village_to_clinic[i] = nearest_clinic
    roads[i][nearest_clinic] = BUILT
    road_lengths[i][nearest_clinic] = distances[i][nearest_clinic]

# 计算所有村庄到最近的医疗点的距离
S1 = sum(min(distances[i]) for i in range(village_num))

# 循环直到没有村庄需要连接到其他的医疗点
while True:
    # 初始化最小距离和对应的村庄和医疗点下标
    min_dist = sys.maxsize
    min_village = -1
    min_clinic = -1

    # 找出最小距离和对应的村庄和医疗点下标
    for i, village in enumerate(villages):
        for j, clinic in enumerate(clinics):
            if village_to_clinic[i] != j:
                dist = distance(village, clinic)
                if dist < min_dist:
                    min_dist = dist
                    min_village = i
                    min_clinic = j

    # 如果没有村庄需要连接到其他的医疗点，跳出循环
    if min_village == -1 or min_clinic == -1:
        break

    # 连接村庄和医疗点，并更新距离矩阵和记录每个村庄连接到的最近医疗点的下标
    roads[min_village][min_clinic] = BUILT
    road_lengths[min_village][min_clinic] = min_dist
    village_to_clinic[min_village] = min_clinic

# 计算连接的道路长度之和
S2 = sum(sum(road_lengths[i]) for i in range(village_num))

# 输出结果
print("S1:", S1)
print("S2:", S2)
print("Clinic locations:", clinics)

运行结果如下：

S1: 12121.619031745784
S2: 2059.076684091099
Clinic locations: [(833.110832319914, 143.4200416352765), (865.178635744262, 773.4847525008886), (68.9101748645612, 664.5739073562236)]

根据结果可以看出，建立3个医疗点的最佳位置分别为(833.11, 143.42)，(865.18, 773.48)和(68.91, 664.57)，总距离为12121.62。需要修建的道路总里程为2059.08。