Турніри Школи Олімпійського Резерву "Step by Step"

Рекомендуємо ознайомитися з правилами участі у турнірах Школи Олімпійського Резерву "Step by Step"
Рейтинг учасників турнірів

Практичні графи
класифікація: "hard"
дата старту: 2008-08-26
дата завершення: 2008-09-01
турнір проводить: Зубик В.В.
к-ть учасників:  11 
результати турніру

опис турніру:

Я люблю алгоритм Floyd-Warshall за його простоту… Жаль лише, що він повільний для таких задач :)

Завдання на турнір >>
задача 1. "Haker"
кількість балів: 50

Хакер Вася був прийнятий консультантом по мережевій безпеці у відому фірму – розробника програмного забезпечення. В даний час у Васі така проблема: він пробує визначити, які із серверів компанії можуть бути кращими цілями для мережевих атак. У Васі є інформація про те, що деякі сервера «довіряють» іншим серверам. Якщо нападник взламає сервер, то він автоматично отримає доступ і до тих серверів, що довіряють взламаному. Дальше можна отримати доступ і до інших, що мають у списку «довірених» взламані сервера. І так дальше.

Цінність сервера S є число серверів, що довіряють йому. Зрозуміло, що самі важливі ті сервера, що мають найвищу цінність і їх безпеці треба приділити саме більше уваги. Складіть програму, що зможе визначати сервера, що мають найвищу цінність.

Мережа фірми складається з N комп'ютерів, що перенумеровані числами від 1 до N. Для деяких комп'ютерів описана їх «довіра» у вигляді пари чисел ( a , b ) – комп'ютер a «довіряє» комп'ютеру b. «Довіра» не є взаємною.

Формат вхідних даних. У першому рядку вхідного файлу haker .in дано два цілих числа N i M ( N <=10000), де N - кількість серверів, а M – число відомих «довір» між ними. У наступних M рядках міститься по два цілих числа a, b (1<= a , b <= N ) .

Формат вихідних даних. В одному рядку вихідного файлу haker. out вивести у зростаючому порядку номери серверів, що мають найвищу цінність.

 

Приклад вхідних та вихідних даних.

haker.in

5 4
3 1
3 2
4 3
5 3

haker.out

1 2

 

задача 2. "Mapa"
кількість балів: 50

Залізнодорожна транспортна компанія на протязі поточного року проклала деякі нові шляхи. Після виконання цієї роботи виникла необхідність внести зміни до карти доріг. Зрозуміло, що всім хочеться мати достатньо просту карту. Тому було вирішено видалити з карти всі станції, що мають сполучення лише з двома станціями (тобто, лише один шлях проходить через станцію).

Для вас таке завдання. Є карта залізних доріг. Всі станції перенумеровані від 1 до N. Між станціями, що мають прямі з'єднання, вказані відповідні відстані.

Вам треба видалити всі станції, що мають лише два сполучення і вказати нові відстані між тими станціями, що залишаються на карті.

Формат вхідних даних. У першому рядку вхідного файлу mapa.in дано два цілих числа N i M ( N <=1000), де N - кількість станцій, а M – число доріг між станціями. У наступних M рядках міститься по три цілих числа a, b, d (1<= a , b <= N , d <=1000) , де a, b – номери станцій, а d - відстань між цими станціями. Гарантується, що між будь-якими двома станціями є шлях і що є по крайній мірі дві станції, які безпосередньо не сполучені лише з двома іншими станціями.

Формат вихідних даних. У першому рядку вихідного файлу mapa. out міститься K - число доріг на оновленій карті . У наступних K рядках – по три числа a, b, d, де a, b (a<=b) – номери станцій, а d - відстань між цими станціями. Порядок виведення рядків не є суттєвим. Якщо є декілька варіантів відповідей, то слід виводи лише один із них.

Приклад вхідних та вихідних даних.

mapa.in

4  4
1 2 1
2 3 2
3 4 3
4 2 1

mapa.out

2
1 2 1
2 2 6

 


назад у розділ "Турніри"