Сайт підготовки до олімпіади з інформатики

програмування в С++

Дерево PDF Печать E-mail
Добавил(а) Administrator   
15.01.16 21:05

Теорія графів
Дерево?
Неорієнтовний граф без петель та кратних ребер задано матрицею суміжності. Визначити, чи є цей граф деревом.
Вхідні дані
Перший рядок містить кількість вершин графа n (1 ≤ n ≤ 100). Далі записана матриця суміжності розміром n×n, у якій 1 позначає наявність ребра, 0 - його відсутність. Матриця симетрична відносно головної діагоналі.
Вихідні дані
Виведіть повідомлення YES, якщо граф є деревом, і NO у протилежному випадку.

Вхідні дані
3
0 1 0
1 0 1
0 1 0
Вихідні дані
YES


http://www.e-olymp.com/uk/problems/977

Остове дерево мінімальної ваги
Король країни Аріїв завоював N міст на території сусідніх держав. Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною.
Input format
Перший рядок вхідного файлу містить натуральне число N (1≤N≤100) – кількість міст у країні, а також цілі числа X та Y – координати столиці. Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст. Значення координат по модулю менші 50000.
Output format
Єдиний рядок має містити дійсне число з трьома знаками після коми – сумарну вартість побудованих доріг. Вважайте, що вартість одиниці довжини дороги дорівнює одній умовній одиниці.
Examples

Input in input.txt Output in output.txt
6 0 0
1 1
-1 1
0 2
1 -1
-1 -1
0 -2 8.485

http://134.249.159.199/cgi-bin/new-client?contest_id=24 Задача I

Задачі
AДерево? - http://www.e-olymp.com/uk/problems/977
BОтримай дерево - http://www.e-olymp.com/uk/problems/978
CСума - http://www.e-olymp.com/uk/problems/2157
DПеревірка на неорієнтовність - http://www.e-olymp.com/uk/problems/2470
EВід матриці суміжності до списку ребер - http://www.e-olymp.com/uk/problems/2471
FОперації на графі http://www.e-olymp.com/uk/problems/2472
GДерево - http://www.e-olymp.com/uk/problems/2923
HВід матриці суміжності до списків суміжності - http://www.e-olymp.com/uk/problems/3981
IПоверни мене! - http://www.e-olymp.com/uk/problems/4854

 

Статистика

Пользователей : 261
Статей : 225
Просмотрено статей : 115349

Вход/Регистрация

Нет