图论的实际应用之三 求中心点 (300分)

  • 主题发起人 主题发起人 LeeChange
  • 开始时间 开始时间
L

LeeChange

Unregistered / Unconfirmed
GUEST, unregistred user!
新市区有n个居民小区，有个矩阵a[n, n]存放着各小区之间的距离。如果a[i, j]=0则表示小区i到小区j之间没有直通路径。现在，市政府决定在其中的一个小区建立一所小学，请问建在哪个小区最好。（最好是这样定义的：以上学路程最远的距离来衡量，使得这个距离最小的方案为最优方案）
上一题:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1949490
下一题:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1954974
 
用标号法依次求出每两个居民区之间的最短距离，用数组b[n,n]表示，再计算b中每个居民区到其他居民区的距离和，和最小的便是最好的小区。时间复杂度O(n^3)
 
用求无向图最小树？
 
先用floyd求任两点间的最短距离dist[i,j]
然后用个二重循环即可求出到其余各顶点之和最小的点了
时间复杂度为O(n^3+n^2)
 
to zroge_faint:
此题先要求出任意两点间的距离,用n遍标号法不是个好办法.而且题目不要求距离和最小,只要求最远距离最小.
to laoli:
您可能没有完全理解此题的意思,最小生成树请见
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1947897
to AI:
第一步是对的,但题目比较的不是距离和,而是最远距离.
 
哦，题目没看清楚，又粗心了，汗~
 
得到b[n,n]后把距离和该为求最远的就行了。
 
看看我的這個，如何
數據結構以前看過一點，不是很通。
最近比較忙，我這個解法也沒有給它測試過
{$APPTYPE CONSOLE}
program centre;
const max=100;
type stk=record　//已經處理過的點
s:real;//到參考點的距離
p:integer;//點
end;
type dis=record　
minv:integer;　//這一輪的最遠點
mindis:real;　//此點離參考點的最近距離
end;

var v:array[1..max,1..max] of real;
s:array[1..max] of boolean;
alv:array[1..max] of stk;
i,j,k,sj,n,mv:integer;
min:real;
distance:array[1..max] of dis;
begin
read(n);
for i:=1 to ndo
for j:=1 to ndo
begin
read(v[i,j]);
if v[i,j]=0 then
v[i,j]:=maxint;
end;
fillchar(s,sizeof(s),0);

for i:=1 to ndo
begin
s:=true;
k:=1;
alv[k].p:=i;
alv[k].s:=0;
k:=k+1;

while(k<=n)do
begin
min:=maxint;
for j:=1 to ndo
begin
if s[j] then
continue;
for sj:=1 to k-1do
begin
if (alv[sj].s+v[j,alv[sj].p])<min then
begin
min:=alv[sj].s+v[j,sj];
mv:=j;
end;
end;
end;
s[mv]:=true;
alv[k].p:=mv;
alv[k].s:=min;
k:=k+1;
end;

distance.minv:=alv[n].p;
distance.mindis:=alv[n].s;

end;

min:=maxint;
for i:=1 to ndo
if distance.mindis<min then
mv:=i;

writeln(distance[mv].minv);
writeln(distance[mv].mindis);
end.
 
昨天晚上想起來有一個地方錯了－－沒有重置標志
看了AI最小生成樹的解法，把最大值往上加了點
修改如下
program centre;
const max=100;
type stk=record　//已經處理過的點
s:real;//到參考點的距離
p:integer;//點
end;
type dis=record　
minv:integer;　//這一輪的最遠點
mindis:real;　//此點離參考點的最近距離
end;

var v:array[1..max,1..max] of real;
s:array[1..max] of boolean;
alv:array[1..max] of stk;
i,j,k,sj,n,mv:integer;
min:real;
distance:array[1..max] of dis;
begin
read(n);
for i:=1 to ndo
for j:=1 to ndo
begin
read(v[i,j]);
if v[i,j]=0 then
v[i,j]:=maxint*maxint;
end;

for i:=1 to ndo
begin
fillchar(s,sizeof(s),0);
s:=true;
k:=1;
alv[k].p:=i;
alv[k].s:=0;
k:=k+1;

while(k<=n)do
begin
min:=maxint*maxint;
for j:=1 to ndo
begin
if s[j] then
continue;
for sj:=1 to k-1do
begin
if (alv[sj].s+v[j,alv[sj].p])<min then
begin
min:=alv[sj].s+v[j,sj];
mv:=j;
end;
end;
end;
s[mv]:=true;
alv[k].p:=mv;
alv[k].s:=min;
k:=k+1;
end;

distance.minv:=alv[n].p;
distance.mindis:=alv[n].s;

end;

min:=maxint*maxint;
for i:=1 to ndo
if distance.mindis<min then
mv:=i;
wtiteln(mv);//此為中心點
writeln(distance[mv].minv);//此為離中心點最遠的點
writeln(distance[mv].mindis);//此為兩點之間的距離
end.
 
昨天雙忘了改一個地方，只顧輸入出距離了，沒有輸出中心點，現在原帖上修改一下
問大家一個問題，我沒有怎麼學過圖論，不知那裡有關於這方面的東東啊
 
TP7.0下编译。
const maxn=10;
var graph:array[1..maxn,1..maxn] of real;
i,j,k,n,minpoint:integer;
min,mindist:real;
begin
read(n);
for i:=1 to ndo
for j:=1 to ndo
begin
read(graph[i,j]);
if (graph[i,j]=0) and (i<>j) then
graph[i,j]:=maxint*maxint;
end;
for i:=1 to ndo
for j:=1 to ndo
if i<>j then
for k:=1 to ndo
if graph[i,j]>graph[i,k]+graph[k,j] then
graph[i,j]:=graph[i,k]+graph[k,j];
mindist:=maxint*maxint;
for i:=1 to ndo
begin
min:=maxint*maxint;
for j:=1 to ndo
if i<>j then
if graph[i,j]<min then
min:=graph[i,j];
if min<mindist then
minpoint:=i;
end;
writeln(minpoint);
end.
 
AI太粗心,我要求的是上学最远的距离尽可能小,不是上学最近的距离尽可能小.
 
我……
const maxn=10;
var graph:array[1..maxn,1..maxn] of real;
i,j,k,n,minpoint:integer;
max,mindist:real;
begin
read(n);
for i:=1 to ndo
for j:=1 to ndo
begin
read(graph[i,j]);
if (graph[i,j]=0) and (i<>j) then
graph[i,j]:=maxint*maxint;
end;
for i:=1 to ndo
for j:=1 to ndo
if i<>j then
for k:=1 to ndo
if graph[i,j]>graph[i,k]+graph[k,j] then
graph[i,j]:=graph[i,k]+graph[k,j];
mindist:=maxint*maxint;
for i:=1 to ndo
begin
max:=0;
for j:=1 to ndo
if i<>j then
if graph[i,j]>max then
max:=graph[i,j];
if max<mindist then

begin
minpoint:=i;
mindist:=max;
end;
end;
writeln(minpoint);
end.
 
这还差不多.
 
我最不擅长静态查错
 
多人接受答案了。
 
您必须登录或注册才可回复。

Similar threads

Ray
[转]终于可以发布Delphi下收点OSGI精髓皮毛而设计的插件框架WisdomPluginFramework
回复
4
查看
4K
chlkuei
C
E
怎样分割，利用率最大？(300分)
2
回复
28
查看
411
sing_cee
S
C
一个判断点是否在浮点坐标边界的多边形之内的新算法 (50分)
回复
16
查看
382
henryandpcw
H
D
怎么判断两个方块的间的距离呢?我使用数组实现的一个方块图形.(100分)
回复
5
查看
180
hikehilter
H
G
一个来自实践的算法难题(300分)
2
回复
35
查看
812
Traveller
T
后退
顶部