haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

noip 每日整理

发布时间:2014-06-18 09:56:42  

From 高级本P95

问题描述:

平面上有N个点(N<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一个点到另一点之间的最短路径。

输入:

第一行:整数N

第2行到第N+1行(共N行),每行两个整数X和Y,描述了一个点的坐标(以一个空格分隔)。

第N+2行为一个整数M,表示图中连线的个数。

此后的M行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线。

最后一行 两个整数s和t,分别表示源点和目标点。

输出:

仅一行,一个实数(保留两位小数),表示从s到t的最短路径长度。 样例:

5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5

3 5 1 5 代码:(floyd算法、求任意两点间的最短路径) type

node=record

x,y:integer;

end;

var

g:array[1..100,1..100] of real;

a:array[1..100] of node;

n,m,x,y,i,j,s,k,t:integer;

function distance(i,j:integer):real;

begin

distance:=sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y)); end;

begin

readln(n);

for i:=1 to n do

readln(a[i].x,a[i].y);

for i:=1 to n do

for j:=1 to n do

g[i,j]:=maxint;

readln(m);

for i:=1 to m do

begin

readln(x,y);

g[x,y]:=distance(x,y);

g[y,x]:=g[x,y];

end;

readln(s,t);

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (g[i,k]+g[k,j]<g[i,j]) then

g[i,j]:=g[i,k]+g[k,j];

writeln(g[s,t]:0:2);

End.

From 高级本P97

问题描述:

学校有N台计算机,为了方便数据传输,现在要将他们用数据线连接起来。两台计算机被连接是指他们中间有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的。 当然,如果将任意两台计算机都用数据线连接,费用将是非常庞大的。为了节省费用,我们采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接。

现在由你负责连接这些计算机,你的任务是使任意两台计算机都连通( 不管是直接的或间接的)。

输入:

第一行为整数N(2..100),表示计算机的数目。此后的N行,每行N个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。

输出:

一个整数,表示最小的连接费用。

样例 输入:

3

0 1 2

1 0 1

2 1 0

输出:

2

代码:(kruskal算法、最小生成树问题) var

g:array[1..100,1..100] of integer;

l:array[0..100] of integer;

u:array[0..100] of boolean;

n,i,j,k,total:integer;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do

read(g[i,j]);

fillchar(l,sizeof(l),$7F);

l[1]:=0;

fillchar(u,sizeof(u),1);

for i:=1 to n do

begin

k:=0;

for j:=1 to n do

if u[j] and (l[j]<l[k]) then k:=j;

u[k]:=false;

for j:=1 to n do

if u[j] and (g[k,j]<l[j]) then l[j]:=g[k,j]; end;

total:=0;

for i:=1 to n do

inc(total,l[i]);

writeln(total);

end.

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com