最小生成树算法及其应用说课讲解.ppt

最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用机器蛇【输入】
输入数据的第一行是一个整数n（n≤200）表示参战的机器蛇总数。
以下n行，每行两个整数xi，yi，为第i支机器蛇的战斗位置。
接下来一行是一个整数m（m≤100）表示航母内部可能产生屏蔽的位置。
最后m行，每行四个整数ai，bi，ci，di，表示线段(ai，bi)-(ci，di)处可能有屏蔽，也就是说通讯网络不能跨越这条线段。
【输出】
输出数据应仅包括一个实数，表示建立的通讯网的最短长度，保留3位小数。
如果不能成功建立通讯网，请输出-1.000。算法分析2、套用最小生成树的经典算法求解functioncp(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)；
ifv=0thencp：=0elseifv>0thencp：=1elsecp：=-1；
end；{cp}
functiondist(a，b：integer)：longint；{计算第a条机器蛇和第b条机器蛇间的距离，若ab之间有屏蔽，则距离设为无穷大}
var
i：integer；
begin
dist：=oo；
fori：=1tomdo{如果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)thenexit；
dist：=sqr(s[a].x-s[b].x)+sqr(s[a].y-s[b].y)；
end；{dist}begin
read(n)；{读入数据}
fori：=1tondowiths[i]doread(x，y)；
read(m)；
fori：=1tomdoread(w1[i].x，w1[i].y，w2[i].x，w2[i].y)；
{用Prim算法求最小生成树}
fillchar(ba，sizeof(ba)，0)；{所有机器蛇未访问}
fori：=2tondod[i]：=oo；{最短边长序列初始化}
d[1]：=0；ans：=0；{从机器蛇1出发,通信网的最短长度初始化}
fori：=1tondobegin{访问n条机器蛇}
min：=oo；{在所有未访问的机器蛇中寻找与已访问的机器蛇相连且具有最短边长的机器蛇k}
forj：=1tondoifnotba[j]and(d[j]<min)thenbegin
k：=j；min：=d[j]；
end；{then}
ifmin=oothenbeginans：=-1；break；end；{then}{若这样的机器蛇不存在，则无解退出}
ans：=ans+sqrt(min)；ba[k]：=true；{最短边长计入通信网,机器蛇k已访问}
forj：=1tondo{机器蛇k出发的所有不受屏蔽的边中，寻找边长最短的（k，j）}
beginmin：=dist(k，j)；ifmin<d[j]thend[j]：=min；end；{for}
end；{for}
writeln(ans：0：3)；{输出通信网的最短长度}
end.{main}