Скачать программы    Все программы автора

ПОГОДНЫЕ УСЛОВИЯ

Система рейсов авиакомпании OlympAirways была спроектирована таким образом, чтобы из любого аэропорта, который обслуживается авиакомпанией, можно было перелететь в любой другой аэропорт, воспользовавшись, возможно, больше чем одним рейсом. Каждый рейс соединяет два аэропорта, и выполняется в обе стороны.Существует проблема, что некоторые рейсы определенное время могут не выполняться из-за плохих погодных условий. Таким образом, вероятно, что клиент не сможет перелететь из аэропорта A аэропорт B, пользуясь только самолетами авиакомпании OlympAirways. Для исследования подобных ситуаций научный отдел компании ввел понятие числа уязвимости связи между парой аэропортов A и B. Это число равно количеству рейсов авиакомпании, отмена любого из которых (при условии, что все остальные рейсы выполняются в обычном порядке) приведет к невозможности перелета в аэропорт B из аэропорта A.

Задание

Напишите программу WEATHER, которая по информации обо всех рейсах, выполняемых авиакомпанией, определяет сумму чисел уязвимости связи между всеми парами аэропортов.

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

Первая строка входного файла WEATHER.DAT содержит целое число N (1≤N≤100) – количество аэропортов, которые обслуживаются авиакомпанией. Вторая строка содержит целое число M (1≤M≤4950) — количество рейсов, выполняемых авиакомпанией. Каждая из последующих M строк задает рейс, который представлен парой целых чисел от 1 до N – номерами аэропортов, которые он соединяет.

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

Единственная строка выходного файла WEATHER.SOL должна содержать целое число — суммарное число уязвимости связи между всеми разными парами аэропортов A и B, таких, что номер A меньше номера B.

Пример входных и выходных данных

{ bp } 

(* Problem : WEATHER*)

const MaxN = 100;

MaxM = 10000;

type tedge = array[1..MaxM,1..2] of integer;

sedge = ^tedge;

var edge : sedge;

count : array[1..MaxN+1] of integer;

N,M : integer;

Res : longint;

a,b : array[1..maxN] of integer; {notes}

mark : array[1..maxN] of boolean;

numb : integer;

const fileinput = 'WEATHER.DAT';

fileoutput = 'WEATHER.SOL';

procedure ReadData; {Read data from file}

var i : integer;

begin

assign(input,fileinput);

reset(input);

readln(N);

readln(M);

for i:=1 to M do

begin

readln(edge^[2*i-1,1],edge^[2*i-1,2]);

edge^[2*i,1]:=edge^[2*i-1,2];

edge^[2*i,2]:=edge^[2*i-1,1]

end;

M:=M*2;

close(input)

end;

procedure SortData; {Sort edge's array with time O(M)}

var i : integer;

edges : sedge;

begin

fillchar(count,sizeof(count),0);

for i:=1 to M do

inc(count[edge^[i,1]]);

for i:=2 to succ(N) do

inc(count[i],count[pred(i)]);

new(edges);

for i:=1 to M do

begin

edges^[count[edge^[i,1]]]:=edge^[i];

dec(count[edge^[i,1]])

end;

dispose(edge);

edge:=edges

end;

procedure WriteData; {Write result}

begin

assign(output,fileoutput);

rewrite(output);

writeln(Res);

close(output)

end;

function Work(curent,parent : integer) : integer; {Depth search and calculating}

var i,s,r : integer;

begin

r:=1;

inc(numb);

a[curent]:=numb;

mark[curent]:=true;

b[curent]:=a[curent];

for i:=succ(count[curent]) to count[succ(curent)] do

if mark[edge^[i,2]] then

begin

if (edge^[i,2]<>parent) and (a[edge^[i,2]]<b[curent]) then

b[curent]:=a[edge^[i,2]]

end

else

begin

s:=Work(edge^[i,2],curent);

if b[edge^[i,2]]>a[curent] then

inc(Res,s*(N-s));

if b[edge^[i,2]]<b[curent] then

b[curent]:=b[edge^[i,2]];

inc(r,s)

end;

Work:=r

end;

procedure Calculate; {Calc result}

begin

Res:=0;

fillchar(a,sizeof(a),0);

b:=a;

fillchar(mark,sizeof(mark),false);

numb:=0;

Work(1,0)

end;

begin

new(edge);

ReadData;

SortData;

Calculate;

WriteData;

dispose(edge)

end.