Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.90
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
#1

Алгоритм Крускала - C++

13.04.2012, 21:56. Просмотров 4138. Ответов 2
Метки нет (Все метки)

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

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

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

Всего домиков N. По карте ребята вычислили координаты каждого домика (Xi, Yi) в целых числах и выписали их на бумаге. За единицу измерения координат они взяли один метр. Однако возник вопрос: Какие домики нужно соединять веревочным телеграфом, чтобы связь была между всеми домиками (возможно, через другие домики), а общая длина всех веревок была как можно меньше?

Требуется написать программу, которая по координатам домиков определяла бы, какова минимальная общая длина всех веревок, соединяющих все домики между собой (возможно, через другие домики).
Порядок ввода:
N
X1 Y1
X2 Y2
...
XN YN
Порядок вывода:
X.xx
где X.xx - минимальная общая длина веревки с точностью до двух знаков в дробной части.
Пример ввода:
5
100 200
200 200
300 400
400 200
400 100
Пример вывода:
623.61
Органичения:
0 < N <= 100
-32000 <= Xi, Yi <= 32000
я решил ее с помощью алгоритма Прима
вот мое решение
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
43
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#define INF 1000000000
using namespace std;
int main()
{
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    int n;
    cin >> n;
    vector< vector<float> > g(n,vector<float>(n,0));
    vector<int> x(n),y(n);
    for (int i=0;i<n;i++)
        cin >> x[i] >> y[i];
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            g[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    vector<bool> used(n);
    vector<float> min_e(n,INF);
    vector<int> sel_e(n,-1);
    min_e[0]=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;
        for (int j=0;j<n;j++)
            if (!used[j] && g[v][j]<min_e[j])
            {
                min_e[j]=g[v][j];
                sel_e[j]=v;
            }
    }
    float dist=0;
    for (int i=1;i<n;i++)
        dist+=g[i][sel_e[i]];
    cout << std::fixed << setprecision(2) << dist;
    return 0;
}
но некак немогу решить ее с помощью алгоритма Крускала
вот мой код
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> p;
vector<int> r;
void make_set(int v)
{
    p[v]=v;
    r[v]=0;
}
int find_set(int v)
{
    return (v==p[v] ? v : p[v]=find_set(p[v]));
}
void union_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if (a!=b)
    {
        if (r[a]<r[b])
            swap(a,b);
        p[b]=a;
        if (r[a]==r[b])
            ++r[a];
    }
}
int main()
{
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    int n,m=0;
    vector< pair< float,pair<int,int> > > g;
    cin >> n;
    p.resize(n);
    r.resize(n);
    vector<int> x(n),y(n);
    for (int i=0;i<n;i++)
    {
        cin >> x[i] >> y[i];
        make_set(i);
    }
    for (int i=0;i<n-1;i++)
        for (int j=i+1;j<n;j++)
        {
            ++m;
            g.push_back(pair< float,pair<int,int> >(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])),pair<int,int>(i,j)));
        }
    sort(g.begin(),g.end());
    float dist=0;
    for (int i=0;i<m;i++)
        if (find_set(g[i].second.first)!=find_set(g[i].second.second))
        {
            dist+=g[i].first;
            union_sets(g[i].second.first,g[i].second.second);
        }
    cout << ios::fixed << setprecision(2) << dist;
    return 0;
}
но он выдает неправильный ответ. Пожалуйста помогите исправить мой код
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2012, 21:56
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Крускала (C++):

Алгоритм Крускала - C++
Помогите найти ошибку в алгоритме.Он и работает как то не так и при выводе результатов еще и ошибку выводит.Код писал на кодеблоксе. ...

Алгоритм, обратный алгоритму Крускала - C++
Требуется реализовать алгоритм поиска максимального остовного дерева

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Помогите алгоритм для char переделать в алгоритм для float - C++
char* DecToBin(char x, char* str) { int i; for (i = sizeof(x)*8-1; i&gt;=0; i--) { str = (x&amp;1 == 1) ? '1' : '0'; x = x &gt;&gt;...

Волновой алгоритм (алгоритм Ли) - C++
Здравствуйте! У кого-нибудь есть реализованный волновой алгоритм (алгоритм Ли) ? Дело в том, что я игрушку захотел написать (что-то...

2
(SkyNet)
22 / 40 / 6
Регистрация: 25.10.2011
Сообщений: 175
13.04.2012, 21:58 #2
Алгоритм Дейстри или Флойда
0
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
13.04.2012, 22:04  [ТС] #3
Цитата Сообщение от (SkyNet) Посмотреть сообщение
Алгоритм Дейстри или Флойда
во первых не Дейстра а Дейкстра, а во вторых кокое это имеет отношение к моему вопросу
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2012, 22:04
Привет! Вот еще темы с ответами:

Алгоритм Крускала и Прима - Алгоритмы
Здраствуйте, алгоритм Крускала и Прима можна ли использовать для отрицательных значений ребер графа? Если нет, то почему?

Алгоритм Прима, Крускала - Delphi
Нашел код реализации алгоритмов, пробовал сделать форму но выдает кучу ошибок. program Project1; uses Forms, Unit1 in...

Алгоритм Крускала (Краскала) на Assembler - Assembler
Добрый день! Кто-то имеет программную реализацию алгоритма Крускала (Краскала) на FASM???

Алгоритм Прима-Крускала - нужен пример - Delphi
Народ , подскажите пожалуйста , где можно найти принцип алгоритма прима - краскла . Вообще все интересует по этой теме , по этому если не...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.