ВСЕ ОТЛИЧНО
Информация о работе
Подробнее о работе
С++ https://informatics.mccme.ru/ Задача №605. Связанное множество
- 1 страниц
- 2018 год
- 23 просмотра
- 1 покупка
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Даны несколько точек на плоскости, некоторые из которых соединены отрезками. Множество точек называется связанным, если из любой его точки можно перейти в любую точку, перемещаясь только по отрезкам (переходить с отрезка на отрезок возможно только в точках исходного множества). Можно за определенную плату добавлять новые отрезки (стоимость добавления равна длине добавляемого отрезка). Требуется за минимальную стоимость сделать данное множество связанным.
Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество точек. Далее в N строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число M – количество уже существующих отрезков. В следующих M строках записаны по 2 числа – номера начала и конца соответствующего отрезка.
Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения с точностью 5 знаков после запятой.
#include
#include
#include
using namespace std;
int n, m;
struct pp {
int x, y;
};
pp a[1000];
bool used[1000];
int c[1000], t[1000], b[1000][1000], d[1000][1000];
const int INF = 1e7;
int main()
{
cin >> n;
for (int i = 1; i > a[i].x >> a[i].y;
}
cin >> m;
for (int i = 1; i
Задача №605. Связанное множество
Даны несколько точек на плоскости, некоторые из которых соединены отрезками. Множество точек называется связанным, если из любой его точки можно перейти в любую точку, перемещаясь только по отрезкам (переходить с отрезка на отрезок возможно только в точках исходного множества). Можно за определенную плату добавлять новые отрезки (стоимость добавления равна длине добавляемого отрезка). Требуется за минимальную стоимость сделать данное множество связанным.
Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество точек. Далее в N строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число M – количество уже существующих отрезков. В следующих M строках записаны по 2 числа – номера начала и конца соответствующего отрезка.
Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения с точностью 5 знаков после запятой.
https://informatics.mccme.ru/
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
