Algorithm 版 (精华区)
发信人: sino (茶水先生), 信区: Algorithm
标 题: ZSUCPC 2000中山同志们的题解--第一试第4题
发信站: 哈工大紫丁香 (2001年08月27日10:10:59 星期一), 站内信件
发信人: splutter (呆子), 信区: ACMICPC
标 题: [合集]第一试第四题 forgetful
发信站: 逸仙时空 Yat-sen Channel (Tue Jun 19 05:26:09 2001), 站内信件
发信人: woodmen (CS99-:悟得慢), 信区: Programming
标 题: [合集]第一试第四题
发信站: 逸仙时空 Yat-sen Channel (Thu May 17 17:38:33 2001), 站内信件
mk (逐风) 于Fri May 11 18:46:04 2001提到：
第四题 Internet消息发布 （50分）
问题描述：设Internet上有N个站点，通常从一个站点发送消息给其他
N－1个站点，需依次发送N－1次。这样从一个站点发布消息传遍N个站点时，可能要较长
时间。而当一个站点发布消息给另一个站点后，已获得消息的这两个站点就可以同时发
布消息给另外两个站点，此后就有四个站点可以同时发布消息，这种发布消息方法应该
会缩短消息传遍N个站点的时间。
请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出从
第一个站点开始发布消息传遍N个站点的最短时间。
输入：由文件Internet.dat输入数据，文件的第一行是Internet上的站点数N（1<=N<=1
0000），第二行起是邻接矩阵严格的下三角部分，各行是整数或字符X。A(I, J)表示从
I站点发送消息给J站点所需要的时间。假设网络是无方向的，故A(I, J)＝A(J, I)，当
A(I, J)＝X时，表示从站点I不能直接向站点J发送消息；A(I, I)＝0表示没有必要自己
给自己送消息（1<=I<=N），严格的下三角阵表示如下：
A(2, 1)
A(3, 1), A(3, 2)
A(4, 1), A(4, 2), A(4, 3)
┇
A(N, 1), A(N, 2)……A(N, N-1)
文件名由键盘输入。
输出：从屏幕上输出，输出只有一行，它是一个非负整数，若为0表示无解，非0表示合
符题意的最小整数。
输入样例：
5
50
30 5
100 20 50
10 X X 10
输出样例：
35
Holmaming (更加风采动朝端) 于Fri May 11 23:30:52 2001提到：
最长的最短路
【 在 mk (逐风) 的大作中提到: 】
: 第四题 Internet消息发布 （50分）
: 问题描述：设Internet上有N个站点，通常从一个站点发送消息给其他
: N－1个站点，需依次发送N－1次。这样从一个站点发布消息传遍N个站点时，可能要较
长
: 时间。而当一个站点发布消息给另一个站点后，已获得消息的这两个站点就可以同时
发
: 布消息给另外两个站点，此后就有四个站点可以同时发布消息，这种发布消息方法应
该
: 会缩短消息传遍N个站点的时间。
: 请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出
从
: 第一个站点开始发布消息传遍N个站点的最短时间。
: 输入：由文件Internet.dat输入数据，文件的第一行是Internet上的站点数N（1<=N<
=1
: 0000），第二行起是邻接矩阵严格的下三角部分，各行是整数或字符X。A(I, J)表示
从
: …………
mysunshine (雨一直下) 于Fri May 11 23:32:31 2001提到：
n=10000的时候，怎么把矩阵存下来？
【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: 最长的最短路
: 【 在 mk (逐风) 的大作中提到: 】
: : 第四题 Internet消息发布 （50分）
: : 问题描述：设Internet上有N个站点，通常从一个站点发送消息给其他
Holmaming (更加风采动朝端) 于Fri May 11 23:34:39 2001提到：
忘记当时是怎么做的了……现在的当务之急是背体育理论，下次再告诉你。
hoho~~~~~~
【 在 mysunshine (雨一直下) 的大作中提到: 】
: n=10000的时候，怎么把矩阵存下来？
: 【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: : 最长的最短路
mysunshine (雨一直下) 于Fri May 11 23:35:16 2001提到：
师弟。。。。
【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: 忘记当时是怎么做的了……现在的当务之急是背体育理论，下次再告诉你。
: hoho~~~~~~
: 【 在 mysunshine (雨一直下) 的大作中提到: 】
: : n=10000的时候，怎么把矩阵存下来？
Thomson (不想灌水) 于Fri May 11 23:36:50 2001提到：
应该是计算一下每两个点的最短距离，然后依次尝试使用各个点作为信息源。
【 在 mk (逐风) 的大作中提到: 】
: 第四题 Internet消息发布 （50分）
: 问题描述：设Internet上有N个站点，通常从一个站点发送消息给其他
: N－1个站点，需依次发送N－1次。这样从一个站点发布消息传遍N个站点时，可能要较
长
: 时间。而当一个站点发布消息给另一个站点后，已获得消息的这两个站点就可以同时
发
: 布消息给另外两个站点，此后就有四个站点可以同时发布消息，这种发布消息方法应
该
: 会缩短消息传遍N个站点的时间。
: 请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出
从
: 第一个站点开始发布消息传遍N个站点的最短时间。
: 输入：由文件Internet.dat输入数据，文件的第一行是Internet上的站点数N（1<=N<
=1
: 0000），第二行起是邻接矩阵严格的下三角部分，各行是整数或字符X。A(I, J)表示
从
: …………
mysunshine (雨一直下) 于Fri May 11 23:37:47 2001提到：
问题是，数据太大了
【 在 Thomson (不想灌水) 的大作中提到: 】
: 应该是计算一下每两个点的最短距离，然后依次尝试使用各个点作为信息源。
: 【 在 mk (逐风) 的大作中提到: 】
: : 第四题 Internet消息发布 （50分）
: : 问题描述：设Internet上有N个站点，通常从一个站点发送消息给其他
legend (爱老婆培训班毕�) 于Fri May 11 23:42:13 2001提到：
考试时好像是改了题目，改成100了
【 在 mysunshine (雨一直下) 的大作中提到: 】
: n=10000的时候，怎么把矩阵存下来？
: 【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: : 最长的最短路
Thomson (不想灌水) 于Fri May 11 23:44:25 2001提到：
100还是很大的吧
【 在 legend (爱老婆培训班毕�) 的大作中提到: 】
: 考试时好像是改了题目，改成100了
: 【 在 mysunshine (雨一直下) 的大作中提到: 】
: : n=10000的时候，怎么把矩阵存下来？
mysunshine (雨一直下) 于Fri May 11 23:44:40 2001提到：
哦，那好办
【 在 legend (爱老婆培训班毕�) 的大作中提到: 】
: 考试时好像是改了题目，改成100了
: 【 在 mysunshine (雨一直下) 的大作中提到: 】
: : n=10000的时候，怎么把矩阵存下来？
Thomson (不想灌水) 于Fri May 11 23:50:50 2001提到：
用我那个方法的话，找两点的最近距离用什么方法好一点？
【 在 mysunshine (雨一直下) 的大作中提到: 】
: 哦，那好办
: 【 在 legend (爱老婆培训班毕�) 的大作中提到: 】
: : 考试时好像是改了题目，改成100了
mysunshine (雨一直下) 于Fri May 11 23:51:56 2001提到：
三重循环
【 在 Thomson (不想灌水) 的大作中提到: 】
: 用我那个方法的话，找两点的最近距离用什么方法好一点？
: 【 在 mysunshine (雨一直下) 的大作中提到: 】
: : 哦，那好办
Thomson (不想灌水) 于Fri May 11 23:54:15 2001提到：
具体怎么办?标号法？
【 在 mysunshine (雨一直下) 的大作中提到: 】
: 三重循环
: 【 在 Thomson (不想灌水) 的大作中提到: 】
: : 用我那个方法的话，找两点的最近距离用什么方法好一点？
monster@argo (不再堕落，不再�) 于Fri May 11 23:58:47 2001)
提到：
转信站: argo
【 在 Thomson (不想灌水) 的大作中提到: 】
: 具体怎么办?标号法？
: 【 在 mysunshine (雨一直下) 的大作中提到: 】
: : 三重循环
for i = 1 to n
for j = 1 to n
c(i, j, 0) = a(i, j)
next
next
for k = 1 to n
for i = 1 to n
for j = 1 to n
if c(i, j, k-1) + c(k, j, k - 1) < c(i, j, k - 1) then
c(i, j, k) = c(i, j, k-1) + c(k, j, k - 1)
else
c(i, j, k) = c(i, j, k - 1)
end if
next
next
next
Thomson (不想灌水) 于Sat May 12 00:12:27 2001提到：
1000000次会不会久了一点
【 在 monster@argo (不再堕落，不再�) 的大作中提到: 】
: 【 在 Thomson (不想灌水) 的大作中提到: 】
: : 具体怎么办?标号法？
: for i = 1 to n
: for j = 1 to n
: c(i, j, 0) = a(i, j)
: next
: next
: for k = 1 to n
: for i = 1 to n
: for j = 1 to n
: …………
monster@argo (不再堕落，不再�) 于Sat May 12 00:16:58 2001)
提到：
转信站: argo
【 在 Thomson (不想灌水) 的大作中提到: 】
: 1000000次会不会久了一点
: 【 在 monster@argo (不再堕落，不再�) 的大作中提到: 】
: : for i = 1 to n
: : for j = 1 to n
o(n^3)是大了点，不过还没想到有什么其他方法。。。
Thomson (不想灌水) 于Sat May 12 00:26:27 2001提到：
【 在 monster@argo (不再堕落，不再�) 的大作中提到: 】
: 【 在 Thomson (不想灌水) 的大作中提到: 】
: : 具体怎么办?标号法？
: for i = 1 to n
: for j = 1 to n
: c(i, j, 0) = a(i, j)
: next
: next
: for k = 1 to n
: for i = 1 to n
: for j = 1 to n
: if c(i, j, k-1) + c(k, j, k - 1) < c(i, j, k - 1) then
~~~~~~~~~~~~~~~~~~~~~~~~~~~~这个地方解释一下吧
: c(i, j, k) = c(i, j, k-1) + c(k, j, k - 1)
: else
: c(i, j, k) = c(i, j, k - 1)
: end if
: next
: next
: next
monster@argo (不再堕落，不再�) 于Sat May 12 00:28:13 2001)
提到：
转信站: argo
【 在 Thomson (不想灌水) 的大作中提到: 】
: 【 在 monster@argo (不再堕落，不再�) 的大作中提到: 】
: : for i = 1 to n
: : for j = 1 to n
: : for j = 1 to n
: : if c(i, j, k-1) + c(k, j, k - 1) < c(i, j, k - 1) then
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~这个地方解释一下吧
从i ==> k有两种途径，一是i => k => j， 另一个是 i => j
然后比较两种方法的cost，取较小的那种
Thomson (不想灌水) 于Sat May 12 00:31:41 2001提到：
【 在 monster@argo (不再堕落，不再�) 的大作中提到: 】
: 标 题: Re: 第一试第四题
: 发信站: Yat-sen Channel BBS (Sat May 12 00:28:13 2001)
: 转信站: argo
:
:
: 【 在 Thomson (不想灌水) 的大作中提到: 】
: : 【 在 monster@argo (不再堕落，不再�) 的大作中提到: 】
: : : for i = 1 to n
: : : for j = 1 to n
: : : for j = 1 to n
: : : if c(i, j, k-1) + c(k, j, k - 1) < c(i, j, k - 1) then
~~~这里为什么不是k
:
: 从i ==> k有两种途径，一是i => k => j， 另一个是 i => j
~~j吧
: 然后比较两种方法的cost，取较小的那种
:
:
: --
: You know, Dr. B.Stroustrup ever said:
:
: Java is not platform-independent,
: it is the platform.
:
: ※ 修改:．monster 于 May 12 00:28:51 修改本文．[FROM: 172.16.16.35]
monster@argo (不再堕落，不再�) 于Sat May 12 00:32:56 2001)
提到：
转信站: argo
【 在 Thomson (不想灌水) 的大作中提到: 】
: 【 在 monster@argo (不再堕落，不再�) 的大作中提到: 】
: : 标 题: Re: 第一试第四题
: : 发信站: Yat-sen Channel BBS (Sat May 12 00:28:13 2001)
: : 转信站: argo
: ~~~这里为什么不是k
: : 从i ==> k有两种途径，一是i => k => j， 另一个是 i => j
: ~~j吧
呵呵，不好意思，一时手快
monster@argo (不再堕落，不再�) 于Sat May 12 02:38:01 2001)
提到：
转信站: argo
【 在 mk (逐风) 的大作中提到: 】
: 第四题 Internet消息发布 （50分）
: 问题描述：设Internet上有N个站点，通常从一个站点发送消息给其他
: N－1个站点，需依次发送N－1次。这样从一个站点发布消息传遍N个站点时，可能要较
长
: 时间。而当一个站点发布消息给另一个站点后，已获得消息的这两个站点就可以同时
发
: 布消息给另外两个站点，此后就有四个站点可以同时发布消息，这种发布消息方法应
该
: 会缩短消息传遍N个站点的时间。
: 请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出
从
: 第一个站点开始发布消息传遍N个站点的最短时间。
: 输入：由文件Internet.dat输入数据，文件的第一行是Internet上的站点数N（1<=N<
=1
: 0000），第二行起是邻接矩阵严格的下三角部分，各行是整数或字符X。A(I, J)表示
从
: …………
只测试过题中数据 ：-）
program imsg;
uses
SysUtils;
var
N: Integer;
C: array [1..100, 1..100] of Word;
const
MaxWord = 65535;
procedure Init;
var
F: Text;
S: String;
I, J: Integer;
begin
FillChar(C, SizeOf(C), 255);
Write('Filename: ');
Readln(S);
AssignFile(F, S);
Reset(F);
Readln(F, N);
for I := 2 to N do
for J := 1 to I - 1 do
begin
Read(F, S);
{ X would cause a default value MaxWord here }
C[I, J] := StrToIntDef(S, MaxWord);
C[J, I] := C[I, J];
end;
CloseFile(F);
end;
procedure Solve;
var
I, J, K: Integer;
S, MinS: Word;
begin
for K := 1 to N do
for I := 1 to N do
for J := 1 to N do
begin
if (C[I][K] < MaxWord) and (C[K][J] < MaxWord) and
((C[I][K] + C[K][J] < C[I][J]) or (C[I][J] = MaxWord)) then
begin
C[I][J] := C[I][K] + C[K][J];
end;
end;
MinS := MaxWord;
for I := 1 to N do
begin
S := 0;
for J := 1 to N do
begin
if (I <> J) and (S < C[I][J]) then S := C[I][J];
end;
if S < MinS then MinS := S;
end;
Writeln(S);
end;
begin
Init;
Solve;
end.
legend (爱老婆培训班毕�) 于Sat May 12 09:37:33 2001提到：
照这样求最短路径最大值之最小者岂不是得25， 不是35啊
【 在 monster@argo (不再堕落，不再�) 的大作中提到: 】
: 【 在 mk (逐风) 的大作中提到: 】
: : 第四题 Internet消息发布 （50分）
: : 问题描述：设Internet上有N个站点，通常从一个站点发送消息给其他
: : 0000），第二行起是邻接矩阵严格的下三角部分，各行是整数或字符X。A(I, J)表
示从
: : …………
: 只测试过题中数据 ：-）
: program imsg;
: uses
: SysUtils;
: var
: …………
--
撷取生活中每一朵清新的浪花,智慧的浪花 ..汇成音乐的海洋.
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：211.435毫秒