Задача 21 Моя Столица

В некоторой стране каждые два города соединены дорогой с односторонним движением. (Если есть дорога из A в B, то нет дороги из B в A.) Столицей называется город, из которого можно добраться в любой другой город.

Требуется составить программу, которая определяет столицу государства.

Формат входных данных:

Первая строка входного файла INPUT.TXT содержит единственное число N (1  N  100) — количество городов страны. Каждая i-ая из последующих N строк содержит не более (N  1) разделенных пробелом целых чисел — номеров городов, соединенных односторонней дорогой из i-ого города. Если из i-ого города не выходит ни одной дороги, то в этой строке записано число 0.

Формат выходных данных:

Выходной файл INPUT.TXT содержит единственное число K (1  K  N) — номер города, из которого можно добраться в любой другой город страны.

Пример:

Input.txt	Output.txt
4 2 3 3 4 4 1	1

Перебираем все вершины графа и от каждой запускаем обход в глубину.

program z_2;

{$APPTYPE CONSOLE}

uses SysUtils;

var a:array[0..101,0..101] of boolean;

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

q:array[0..101] of integer;

n:integer;

procedure dfs(x:integer);

var i:integer;

begin

inc(q[x]); считаем город

u[x]:=true; отмечаем его

for i:=1 to n do находим соседний с минимальным номером

if a[i,x] and (not u[i]) then dfs(i); и запускаем обход в глубину от него

end;

procedure init;

var i,x:integer;

begin

reset(input,'input.txt');

rewrite(output,'output.txt');

readln(n); считываем количество городов

for i:=1 to n do перебираем их

begin

while not seekeoln do пока не дошли до конца строки

begin

read(x); считываем номер города, связанного с х

if x<>0 then

a[i,x]:=true; отмечаем его в матрице смежности

end;

readln; переводим курсор на новую строку

end;

close(input);

end;

procedure solve;

var i:integer;

begin

fillchar(q,sizeof(q),0); заполняем массив q нулями

for i:=1 to n do поочередно запускаем обход в глубину

от каждого города

begin

fillchar(u,sizeof(u),false);

dfs(i);

end;

end;

procedure out;

var i:integer;

begin

for i:=1 to n do

if q[i]=n then если из вершины i можно добраться до всех городов,

begin write(i); break; end; выводим ее и прерываем цикл

close(output);

halt(0);

end;

begin init; solve; out; end.

графызадачи

Задача 22 Гексагон

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

Н апример, над первой квартирой первого этажа находится квартира с номером 55 (см. план первого этажа на рисунке, N=3). Все гексагонцы ужасные болтуны и не упустят возможности пообщаться с гостем за чашкой чая. Для каждого хозяина квартиры известно, сколько времени он готов провести с гостем. Требуется узнать за какое минимальное время можно добраться из квартиры с номером V до квартиры с номером S, если двигаться можно через общую сторону квартир (как известно, гексагонцы умеют проходить сквозь стены) или в квартиру этажом выше или ниже.

В стране Гексагония количество квартир в доме не превышает одного миллиона.

Формат входного файла

В первой строке - два числа, разделенных пробелами: размер гексагона N и количество этажей M (N, M > 0).

Во второй строке - два числа V и S, разделенные пробелами.

В третьей строке содержится набор натуральных чисел (каждое не превышает 1000000), j-тое из которых соответствует j-той квартире и показывает, сколько времени потребуется провести с хозяином квартиры, если придется через нее проходить. Количество чисел совпадает с количеством квартир в доме.

Формат выходного файла

Выходной файл должен содержать одно число - минимальное время, за которое можно добраться из квартиры с номером V в квартиру с номером S.

Пример

Input.txt	Output.txt
1 1 1 6 1 1 1 1 1 1	2

Задача решается алгоритмом Дейкстры. Предварительно строится взвешенный граф, ребро которого означает возможность перехода из комнаты в комнату.

program z2;

{$APPTYPE CONSOLE}

uses SysUtils;

const ln = 1048576;

inf = 1000000000000000;

var

n,m,i,j,c,r,v,s,mn,new:integer;

E:array[1..1000000,0..5] of integer;

P,W,Res:array[0..1000000] of int64;

B:array[0..1000000] of boolean;

T:array[1.. 2 * ln] of integer;

procedure update(v:integer);

begin

v := v + ln - 1;

v := v div 2;

while v > 0 do

begin

if W[T[2 * v]] < W[T[2 * v + 1]] then

T[v] := T[2 * v]

else

T[v] := T[2 * v + 1];

v := v div 2;

end;

end;

begin

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

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

read(n,m);

c := 0;

fillchar(E,sizeof(E),0);

for j := 1 to n do

begin

r := 2 * (n + j) - 1;

for i := 1 to r do

begin

inc(c);

if i > 1 then

begin

inc(E[c,0]);

E[c,E[c,0]] := c - 1;

end;

if i < r then

begin

inc(E[c,0]);

E[c,E[c,0]] := c + 1;

end;

if (i mod 2 = 1) then

begin

inc(E[c,0]);

if j < n then

E[c,E[c,0]] := c + r + 1

else

E[c,E[c,0]] := c + r;

end;

if (i mod 2 = 0) and (j > 1) then

begin

inc(E[c,0]);

E[c,E[c,0]] := c - r + 1;

end;

end;

end;

for j := n downto 1 do

begin

r := 2 * (n + j) - 1;

for i := 1 to r do

begin

inc(c);

if i > 1 then

begin

inc(E[c,0]);

E[c,E[c,0]] := c - 1;

end;

if i < r then

begin

inc(E[c,0]);

E[c,E[c,0]] := c + 1;

end;

if (i mod 2 = 1) then

begin

inc(E[c,0]);

if j < n then

E[c,E[c,0]] := c - r - 1

else

E[c,E[c,0]] := c - r;

end;

if (i mod 2 = 0) and (j > 1) then

begin

inc(E[c,0]);

E[c,E[c,0]] := c + r - 1;

end;

end;

end;

for i := 6 * n * n + 1 to 6 * n * n * m do

begin

E[i,0] := E[i - 6 * n * n,0];

for j := 1 to E[i,0] do

E[i,j] := E[i - 6 * n * n,j] + 6 * n * n;

end;

for i := 1 to 6 * n * n * m do

begin

if i > 6 * n * n then

begin

inc(E[i,0]);

E[i,E[i,0]] := i - 6 * n * n;

end;

if i < 6 * n * n * m - 6 * n * n then

begin

inc(E[i,0]);

E[i,E[i,0]] := i + 6 * n * n;

end;

end;

read(v,s);

fillchar(T,sizeof(T),0);

for i := 1 to 6 * n * n * m do

begin

read(P[i]);

W[i] := inf;

T[i + ln - 1] := i;

end;

W[0] := inf;

for i := ln - 1 downto 1 do

T[i] := T[2 * i];

fillchar(B,sizeof(B),false);

W[v] := 0;

update(v);

while not B[s] do

begin

mn := T[1];

B[mn] := true;

Res[mn] := W[mn];

for i := 1 to E[mn,0] do

begin

new := E[mn,i];

if B[new] then

continue;

if W[new] > W[mn] + P[new] then

begin

W[new] := W[mn] + P[new];

update(new);

end;

end;

W[mn] := inf;

update(mn);

end;

if v = s then

writeln(0)

else

writeln(Res[s] - P[s]);

close(input);

close(output);

end.

графызадачи

Задача 23 Вавилонская башня

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

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

Для удобства пронумеруем все языки числами от 1 до 50. Во входном файле Input.txt задано количество людей N (1N100), а дальше идут описания того, какие языки знают эти люди. Для каждого человека записано сначала число M_i (0M_i50), определяющее количество языков, известных i-ому человеку, а затем перечисляются номера самих этих языков в возрастающем порядке (номера языков — числа от 1 до 50). Считается, что руководитель строительства — это человек с номером 1.

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

В выходной файл вывести одно число — количество человек, до которых может «дойти» отданная руководителем команда (включая самого руководителя).

Примеры:

Input.txt	Output.txt
5 2 1 2 1 1 2 2 3 0 2 4 5	3
8 3 1 4 8 3 2 4 15 3 12 14 19 2 14 33 2 8 11 4 2 4 18 21 1 15 2 21 23	6

Эта задача на графы. Решается поиском в глубину. Приводим два возможных решения задачи.

program zad3;

var a:array[1..200,1..200]of integer;

u:array[1..200]of boolean;

i,j,n,m,ans,k:integer;

procedure dfs(v:integer); процедура обхода в глубину

var i0:integer;

begin

if v>50 then

begin

u[v]:=true;

inc(ans);

end;

for i0:=1 to 50+n do

if (not u[i0])and(a[v,i0]=1) then dfs(i0);

end;

begin

reset(input,'input.txt');

rewrite(output,'output.txt');

read(n);

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

for i:=1 to n do перебираем людей

begin

read(m); считываем количество языков, которые знает человек

for j:=1 to m do заполняем матрицу смежности

begin

read(k); считываем номер языка

a[k,50+i]:=1;

a[50+i,k]:=1;

end;

end;

fillchar(u,sizeof(u),false);

ans:=0;

dfs(51); запускаем обход в глубину

writeln(ans);

close(input); close(output);

end.

Вот второе решение с использование множества.

Const InputFile='Input.TxT';

OutputFile='Output.TxT';

MaxN=100;

MaxK=50;

Type Sset=Set Of 1..50; тип - множество

Var A: Array[1..MaxN] Of Sset; массив множеств языков, которые знают люди

was: Array[1..MaxN] Of Boolean; массив флагов (рассмотрен человек или нет)

N: Integer;

cnt: Integer;

Procedure Init;

Var i, j, sc, p: Integer;

Begin

FillChar(A, SizeOf(A), 0); заполняем массивы нулями

FillChar(was, SizeOf(was), 0);

cnt:=0;

Assign(Input, InputFile);

Reset(Input);

Read(N);

For i:=1 To N Do Begin перебираем людей

Read(sc); считываем количество языков, которые знает человек

For j:=1 To sc Do Begin

Read(p);

Include(A[i], p); добавляем язык в множество

End;

End;

Close(Input);

End;

Procedure Rec(Const p: Integer); рекурсивная процедура обхода в глубину

Var i: Integer;

Begin

If was[p] Then Exit; если человек рассмотрен, то возвращаемся на один

шаг назад

was[p]:=True; Inc(cnt); отмечаем человека и считаем его

For i:=1 To N Do перебираем людей

If A[i]*A[p]<>[] Then Rec(i); если пересечение множеств пусто, т.е. i человек не

рассмотрен, то запускаем рекурсию от него

End;

Procedure Out; процедура вывода результатов

Begin

Assign(Output, OutputFile); Rewrite(Output);

WriteLn(cnt);

Close(Output);

End;

begin Init; Rec(1); Out; end.

графызадачи

Задача 24 Стабильныйколлектив нет решения

В фирме OAO "Новый Софт" работа совсем не идёт, фирма несёт убытки, а всё из-за того, что рабочий коллектив не дружен, а правильные отношения не налажены.

Директор фирмы, Пётр Новиков, решил принять радикальные меры, а именно, уволить часть сотрудников, чтобы остался максимально стабильный коллектив.

Для начала, необходимо выяснить, кто с кем дружит (известно, что дружба всегда взаимна). Затем, на основании этих данных найти коллектив (непустое подмножество сотрудников) с максимальной стабильностью.

Стабильность коллектива A определяется слабым звеном. Слабое звено коллектива A — это человек, у которого меньше всего друзей в коллективе A. Число друзей у слабого звена и есть стабильность коллектива.

Да, и ещё — Петр Новиков хотел бы остаться работать в фирме и себя он увольнять не собирается, хотя, в принципе, он может быть слабым звеном. Известно, что у Петра Новикова есть друзья среди своих сотрудников.

Помогите Петру и напишите программу, которая среди коллективов, в которых он есть, находит коллектив с максимальной стаблильностью. Седи возможных коллективов, удовлетворяющих этому свойству, найдите тот, у которого максимальный размер. Если таких коллективов несколько, то найдите один из возможных.

Вход. В первой строке дано количество M дружных пар, 0 < M < 40000. Затем идёт M строчек, в каждой из которых даны два разных имени, разделённые пробелом. Имена сотрудников записаны латинскими символами и имеют длину менее 32 символов. Имя Петра Новикова записано как Petr. Общее число сотрудников не превосходит 7000. Первая буква любого имени заглавная, а остальные маленькие.

Выход.

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

Input.txt	Output.txt
8 Petr Vasya Petr Kolya Sergey Max Petr Lena Lena Vasya Lena Kolya Vasya Kolya Sergey Lena	4 3 Kolya Lena Petr Vasya

Если бы нам было известно значение K — стабильности искомого коллектива, то есть максимальное значение минимальной степени по всем подграфам? Тогда мы могли бы безбоязненно удалить из графа вершины со степенью меньше K, причём в любом порядке. Задача решается жадным алгоритмом. Помещаем все вершины в очередь. На каждом шаге удаляем "самое слабое звено" — вершину с минимальной степенью — и по ходу вычисляем максимальную степень извлекаемых вершин. Максимальная степень — это и есть искомое K. На втором проходе извлечем все вершины степени меньше K, а оставшиеся вернём как ответ.

графызадачи

К оглавлению