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

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-15

• #1

新市区有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

 

Z

zroge_faint

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-15

• #2

用标号法依次求出每两个居民区之间的最短距离，用数组b[n,n]表示，再计算b中每个居民区到其他居民区的距离和，和最小的便是最好的小区。时间复杂度O(n^3)

 

L

laoli

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-15

• #3

用求无向图最小树？

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-15

• #4

先用floyd求任两点间的最短距离dist[i,j]
然后用个二重循环即可求出到其余各顶点之和最小的点了
时间复杂度为O(n^3+n^2)

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-16

• #5

to zroge_faint:
此题先要求出任意两点间的距离,用n遍标号法不是个好办法.而且题目不要求距离和最小,只要求最远距离最小.
to laoli:
您可能没有完全理解此题的意思,最小生成树请见
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1947897
to AI:
第一步是对的,但题目比较的不是距离和,而是最远距离.

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-16

• #6

哦，题目没看清楚，又粗心了，汗~

 

Z

zroge_faint

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-17

• #7

得到b[n,n]后把距离和该为求最远的就行了。

 

L

lichdr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-17

• #8

看看我的這個，如何
數據結構以前看過一點，不是很通。
最近比較忙，我這個解法也沒有給它測試過
{$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;
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.

 

L

lichdr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-19

• #9

昨天晚上想起來有一個地方錯了－－沒有重置標志
看了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;
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.

 

L

lichdr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-19

• #10

昨天雙忘了改一個地方，只顧輸入出距離了，沒有輸出中心點，現在原帖上修改一下
問大家一個問題，我沒有怎麼學過圖論，不知那裡有關於這方面的東東啊

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-19

• #11

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;
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.

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-19

• #12

AI太粗心,我要求的是上学最远的距离尽可能小,不是上学最近的距离尽可能小.

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-19

• #13

我……
const maxn=10;
var graph:array[1..maxn,1..maxn] of real;
i,j,k,n,minpoint:integer;
max,mindist:real;
begin
read;
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.

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-19

• #14

这还差不多.

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-19

• #15

我最不擅长静态查错

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-19

• #16

多人接受答案了。