День Объединения

10.01.2020, 12:29. Показов 7283. Ответов 0

Метки графы (Все метки)

Студворк — интернет-сервис помощи студентам

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

Короче, решил выложить решение, чтобы такие же бедолаги как я не переписывали его с этого сайта (это же и источник):
https://site.ada.edu.az/~medv/... 0/2967.htm

Вот решение (на с++):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
 
 
using namespace std;
 
int x[5001], y[5001];
int used[5001], min_e[5001], end_e[5001];
 
int dist2(int i, int j) { // расстояне между вершинами i и j графа
    return (x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]);
}
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];
 
    memset(min_e, 0x3F, sizeof(min_e));
    memset(end_e, -1, sizeof(end_e));
    memset(used, 0, sizeof(used));
 
    double dist = min_e[1] = 0;
 
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++)
            if (!used[j] && (v == -1 || min_e[j] < min_e[v])) v = j;
        used[v] = 1;
        if (end_e[v] != -1) dist += sqrt((double) dist2(v, end_e[v]));
        for (int to = 0; to < n; to++) {
            int dV_TO = dist2(v, to);
            if (!used[to] && (dV_TO < min_e[to])) {
                min_e[to] = dV_TO;
                end_e[to] = v;
            }
        }
    }
 
    cout << fixed << setprecision(10) << dist;
}

Всеи удачи

IT_Exp

Эксперт

34794 / 4073 / 2104

Регистрация: 17.06.2006

Сообщений: 32,602

Блог

10.01.2020, 12:29

Ответы с готовыми решениями:

Определить день недели, на который приходится день с датой d (день), m (месяц)
Считая, что год не високосный и его 1 января приходится на день недели wd1, определиь wd -день недели, на который приходится день с датой...

На овощную базу привезли помидоры. В первый день 8 машин по а ящиков; во второй день 6 машин по в ящиков в каждой. В какой день помидоров привезли бол
На овощную базу привезли помидоры. В первый день 8 машин по а ящиков; во второй день 6 машин по в ящиков в каждой. В какой день помидоров...

Розница 2.0 банковские карты, возврат день-в-день одной позиции(из нескольких)
после оформлении возврата (удаления лишних строк, подтверждения оплаты на терминале) возникает ошибка: "Ошибка оплаты чека! Сумма...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

BasicMan

Эксперт

29316 / 5623 / 2384

Регистрация: 17.02.2009

Сообщений: 30,364

Блог

10.01.2020, 12:29

Помогаю со студенческими работами здесь

Вводится k-й день невисокосного года - определить, является ли этот день рабочим.
Вводится k-й (1<=k<=365) день невисокостного года, в котором 1 января – понедельник. Определить, является ли этот день рабочим, если...

Надо выводить день(дата) Программиста. В формате день/месяц/год
День программиста отмечается в 255-й день года (при этом 1 января считается нулевым днем). Требуется написать программу, которая определит...

Дана дата в формате день:месяц:год. Определить день недели
Задание: Дана дата в формате день:месяц:год. Определить день недели.

Определить день недели, на который приходится день с введенной датой
имеются следующие описания:число=1..31 день недели(пн,вт,ср,чт,пт,сб).Считая,что год не високосный и его 1 января приходиться на любой день...

Определить, на какой день недели приходится k-й день невисокосного года
Пусть k – целое от 1 до 365. Присвоить целой переменной n значение 1,2,…6 или 7 в зависимости от того, на какой день недели ( понедельник,...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

Наверх