Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.90
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
13.04.2012, 21:56     Алгоритм Крускала #1
Задача:
Тимур и его друзья, приехав летом на свои старые дачи, решили устроить на время своего отдыха игру. Они организовали команду, чтобы тайно помогать жителям дачного городка в их повседневных делах.

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

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

Всего домиков 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;
}
но он выдает неправильный ответ. Пожалуйста помогите исправить мой код
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2012, 21:56     Алгоритм Крускала
Посмотрите здесь:

C++ Алгоритм
Волновой алгоритм (алгоритм Ли) C++
алгоритм C++
Помогите алгоритм для char переделать в алгоритм для float C++
Алгоритм C++
C++ Алгоритм Крускала
Алгоритм, обратный алгоритму Крускала C++
C++ Алгоритм

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
(SkyNet)
 Аватар для (SkyNet)
22 / 40 / 6
Регистрация: 25.10.2011
Сообщений: 175
13.04.2012, 21:58     Алгоритм Крускала #2
Алгоритм Дейстри или Флойда
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
13.04.2012, 22:04  [ТС]     Алгоритм Крускала #3
Цитата Сообщение от (SkyNet) Посмотреть сообщение
Алгоритм Дейстри или Флойда
во первых не Дейстра а Дейкстра, а во вторых кокое это имеет отношение к моему вопросу
Yandex
Объявления
13.04.2012, 22:04     Алгоритм Крускала
Ответ Создать тему
Опции темы

Текущее время: 01:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru