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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Перевести строку из одной кодировки в другую http://www.cyberforum.ru/cpp-beginners/thread547157.html
Нужно написать программу, перекодирующую строку в кодировке KOI в строку в кодировке Windows-1251 и обратно. Прорыскал пол-инета, но ничего интересного не нашел. Помогите, хотя бы распишите алгоритм решения :) Предполагаемые варианты решения: 1) Считывание из файла в опр. кодировке строки, и дальнейшая "подгонка кусками" под другую кодировку, т.е. все различия между кодировками...
C++ Строки: удалить все пробелы Всем доброго времени суток. Я учусь на инженера-электрика и вообщем-то засел на задаче по программированию на С++. Буду весьма благодарен тому доброму человеку, который отзовётся и поможет моей проблеме. И так, задача (Тема "Нестандартные функции") Написать и протестировать функцию, которая "сжимает" строку, удаляя из неё все пробелы. Символьная строка вводится с клавиатуры. В программе можно... http://www.cyberforum.ru/cpp-beginners/thread547148.html
C++ Преобразование LPVOID в int
Собственно вопрос в коде #include <Windows.h> #include <stdio.h> DWORD WINAPI Func(LPVOID); int main(void) { int a=0; DWORD thID;
Массив строк - список книг определенного автора C++
Подскажите как делать. Если есть дайте ссылку на подобные задачи. Массив строк. Каждая строка содержит: -шифр книги -ФИО автора -год издания -год количество страниц Определить список книг определенного автора, изданных в определенном месте и не ранее указанного года.
C++ Строки - проверка на переполнение и удаление слов http://www.cyberforum.ru/cpp-beginners/thread547125.html
подскажите пожалуйста как для вот этой программы со строками сделать проверку на переполнение, и чтобы когда мы удаляли все слова начинающиеся на гласную букву компилятор выдавал оставшиеся слова только чтобы в начале не было пробела stroka() { char str, s; cout<<"Input stroku:\n"; gets (str); char *stroka = new char ; gets(stroka);
C++ Напечатать в алфавитном порядке буквы Всем привет.Помогитеюу меня есть текст и мне надо напечатать в алфавитном порядке буквы,входящие в заданный текст по одному разу. Я сделал её пузырьковым методом,но как мне убрать дубликаты? подробнее

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

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

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

Всего домиков 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;
}
но он выдает неправильный ответ. Пожалуйста помогите исправить мой код
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 12:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru