- 最小生成树算法是如何设计出来的？我知道该算法是列出一个表，然后一?
- 最小生成树是如何设计出来的？
我知道该算法是列出一个表，然后一条边一条边往上加。
但是这个算法是如何设计出来的？
- 在未来的某次战争中，我军计划了一次行动，目的是劫持敌人的航母。由于这个计划高度保密，你只知道你所负责的一部分：机器蛇的通信网络。计划中要将数百条机器蛇投放到航母的各个角落里。由于航母内部舱室、管线错综复杂，且大部分由金属构成，因此屏蔽效应十分强烈，况且还要考虑敌人的大强度电子干扰，如何保持机器蛇间的联系，成了一大难题。每条机器蛇的战斗位置由作战计划部门制定，将会及时通知你。每条机器蛇上都带有接收、发射系统，可以同时与多条机器蛇通讯。由于整个系统承载的数据量庞大，需要一个固定的通讯网络。情报部门提供了极其详尽的敌方航母图纸，使你对什么地方有屏蔽了如指掌。
请你设计一个程序，根据以上信息构造通讯网络，要求信息可以在任意两条机器蛇间传递，同时为了避免干扰，通讯网络的总长度要尽可能的短。
输入数据的第一行是一个整数n（n≤200）表示参战的机器蛇总数。
以下n行，每行两个整数xi，yi，为第i支机器蛇的战斗位置。
接下来一行是一个整数m（m≤100）表示航母内部可能产生屏蔽的位置。
最后m行，每行四个整数ai，bi，ci，di，表示线段(ai，bi)-(ci，di)处可能有屏蔽，也就是说通讯网络不能跨越这条线段。
【输出】
输出数据应仅包括一个实数，表示建立的通讯网的最短长度，保留3位小数。
如果不能成功建立通讯网，请输出-1.000。
题目中要求信息可以在任意两条机器蛇间传递、通讯网络的总长度要尽可能的短，显然这是一个求图的最小生成树问题。这道题在构造图的过程中还涉及到一点计算几何的知识。
1、判断线段相交
两条线段AB、CD，相交的充要条件是：A、B在直线CD的异侧且C、D在直线AB的异侧。也就是说从AC到AD的方向与从BC到BD的方向不同，从CA到CB的方向也与从DA到DB的方向不同。
以机器蛇为顶点，以不受屏蔽的通信线路为边构建图，就可以直接套用最小生成树的经典算法求解。由于几乎每两条机器蛇间都会有一条边，因此应选用Prim算法。
设
const
maxn=200 ； oo=2000000000；{ 机器蛇数的上限和无穷大}
type
TPoint=record {坐标}
x，y：longint；
end；
var
s，w1，w2：array[1..maxn] of TPoint； { 机器蛇的坐标和屏蔽线的坐标 }
n，m，i，j，k：integer；
ba：array[1..maxn] of boolean； { 机器蛇的访问标志}
d：array[1..maxn] of longint； {d[i]以机器蛇i为头的最短边长}
min：longint；
ans：double；
function cp(p1，p2，p：TPoint)：integer； { 计算矢量PP1*PP2 }
var
v：longint；
begin
v：=(p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.x-p.x)；
if v=0 then cp：=0 else if v>0 then cp：=1 else cp：=-1；
end；{cp}
function dist(a，b：integer)：longint；{ 计算第a条机器蛇和第b条机器蛇间的距离，若ab之间有屏蔽，则距离设为无穷大 }
var
i：integer；
begin
dist：=oo；
for i：=1 to m do { 如果a到b穿过第i个屏蔽，则返回无穷大 }
if (cp(w1[i]，w2[i]，s[a])*cp(w1[i]，w2[i]，s[b])=-1) and
(cp(s[a]，s[b]，w1[i])*cp(s[a]，s[b]，w2[i])=-1) then exit；
dist：=sqr(s[a].x-s[b].x)+sqr(s[a].y-s[b].y)；
end；{ dist }
begin
read(n)；{ 读入数据 }
for i：=1 to n do with s[i] do read(x，y)；
read(m)；
for i：=1 to m do read(w1[i].x，w1[i].y，w2[i].x，w2[i].y)；
{用Prim算法求最小生成树 }
fillchar(ba，sizeof(ba)，0)； {所有机器蛇未访问}
for i：=2 to n do d[i]：=oo； {最短边长序列初始化}
d[1]：=0 ；ans：=0； {从机器蛇1出发,通信网的最短长度初始化}
for i：=1 to n do begin {访问n条机器蛇}
min：=oo；{在所有未访问的机器蛇中寻找与已访问的机器蛇相连且具有最短边长的机器蛇k}
for j：=1 to n do if not ba[j] and (d[j]