Минимальное покрытие

Кратчайший путь в неориентированном графе

В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.

Входные данные

Во входном файле INPUT.TXT записано сначала число N - количество вершин в графе (1<=N<=100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.

Выходные данные

В выходной файл OUTPUT.TXT выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.

Программа

const m=100;

var n,x,y,i,j,ia,ij:integer;

a:array[1..m,1..m] of integer;

r,v:array[1..m] of integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

for i=1 to n do

for j:=1 to n do

read(a[i,j]);

read(x,y);

r[x]:=1;v[1]:=x;ia:=1;ij:=2;

while ia<ij do

begin

for i:=1 to n do

if (a[i,v[ia]]=1) and (r[i]=0) then

begin

r[i]:=r[v[ia]]+1;

v[ij]:=i;

ij:=ij+1

end;

ia:=ia+1

end;

if r[y]=0 then write(-1)

else write(r[y]-1)

end.

Кратчайший путь в ориентированном графе. Алгоритм Дейкстры

Дан ориентированный взвешенный граф. Необходимо найти кратчайшее расстояние от вершины S до вершины F.

Входные данные

В первой строке входного файла INPUT.TXT записаны три числа: N,S и F (1<=N<=100; 1<=S,F<=N), где N – количество вершин графа. В следующих N строках записаны по N чисел - матрица смежности графа, где число в i-ой строке j-ом столбце соответствует ребру из i в j: -1 означает отсутствие ребра между вершинами, а любое неотрицательное целое число (от 0 до 100) - наличие ребра данного веса . На главной диагонали матрицы всегда записаны нули.

Выходные данные

В выходной файл OUTPUT.TXT необходимо вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

Программа

const t=100;

var

i,j,p,n,f,s:longint;

a:array[1..t,1..t] of integer;

d:array[1..t] of integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt');rewrite(output);

read(n,s,f);

for i:=1 to n do

for j:=1 to n do

read(a[i,j]);

for i:=1 to n do

d[i]:=30000;

d[s]:=0;

repeat

p:=0;

for i:=1 to n do

for j:=1 to n do

if (i<>j) and (a[i,j]>=0) and (d[i]<30000) and

(d[i]+a[i,j]<d[j]) then

begin

d[j]:=d[i]+a[i,j];

p:=1

end;

until p=0;

if d[f]=30000 then

write(-1)

else

write(d[f])

end.

Города

Необходимо разработать систему оповещения, которая смогла бы передавать информацию по цепному принципу между городами.

При этом в каждом городе необходимо построить радиостанцию таким образом, чтобы была связь между всеми городами. При этом все такие станции должны передавать сигнал друг другу на равном расстоянии R. Таким образом, будет возможна передачи информации из одного города в другой только тогда, когда расстояние между ними не более R.

По заданным координатам городов, в целях экономии энергии радиостанций, Вам следует определить минимальное значение R, при котором информация сможет быть доставлена из любого города во все остальные.

Входные данные

В первой строке входного файла INPUT.TXT сначала записано натуральное число N – количество городов (N ≤ 1000). Далее идет N строк, содержащих вещественные координаты (X_i,Y_i) соответствующего города. (-10000<=X_i,Y_i<=10000). Предполагается, что все города находятся на плоскости.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно вещественное число – наименьший радиус радиостанций. Число следует вывести с двумя знаками после запятой, без лидирующих нулей, в формате, приведенном в примерах.

Программа

var x,y: array[1..1000] of real;

n,i,j: integer;

max,min,r: real;

begin

assign(input,'input.txt');reset(input);

assign(output,'output.txt');rewrite(output);

readln(n);

if n=1 then begin write ('0.00');halt(0);end;

for i:=1 to n do readln(x[i],y[i]);

max:=0;

min:=sqrt(sqr(x[1]-x[2])+sqr(y[1]-y[2]));

for i:=1 to n do

begin

for j:=1 to n do

if i<>j then

begin

r:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));

if r<min then min:=r;

end;

if min> max then max:=min;

min:=60000000;

end;

max:=max+0.001;

write (max:0:2);

end.

Минимальное покрытие

uses crt,xpm,graph;

const n=9;

var

i,j,k,d,min:integer;

gr:array[1..n,1..n] of byte;

bette,

pokritie:boolean;

gientk,min_pokritie:array[1..n] of byte;

begin

{случайно определяется граф}

randomize;

for i:=1 to n-1 do

for j:=i+1 to n do

if random(10)<8 then

begin

gr[i,j]:=1;

gr[j,i]:=1

end;

{текущая выборка вершин}

for i:=1 to n do

gientk[i]:=0;

{перебор элементов покрытия}

min:=n;

repeat

i:=n;

while gientk[i]=1 do

begin

gientk[i]:=0;

i:=i-1

end;

if i>0 then {еще не перебрали все подмножества }

begin

gientk[i]:=1;

{proverka na pokritie}

pokritie:=true;

for i:=1 to n do

for j:=i+1 to n do

if gientk[i]+gientk[j]+gr[i,j]=3 then

{Если i и j связаны и находятся в множестве, то это не минимальное покрытие}

pokritie:=false;

if pokritie then

begin

d:=0;

for i:=1 to n do

d:=d+gientk[i];

if d<min then

begin

min:=d;

min_pokritie:=gientk

end;

end;

until i=0; { все подмножества перебрали}

writeln(min); {размер минимального покрытия}

{вершины минимального покрытия}

write(‘{ ‘};

for i:=1 to n do

if min_pokritie[i]=1 then

write(i,’ ‘);

write(‘ }‘);

end.