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

задача на систему дорог - C++

Восстановить пароль Регистрация
 
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
23.05.2013, 06:21     задача на систему дорог #1
help с решением
Система дорог
Даны N городов соединенных M дорогами. С любого города можно добраться до любого другого города. Из них оставить дороги, чтобы не осталось циклов и сумма длин оставшихся дорог была минимальна.
Входные данные
В первой строке заданы два целых числа N и M – количество городов и количество дорог. Со второй строки заданы номера городов соединенных дорогами и их длины.
Выходные данные
Напечатать одно число – суммарная длина

Пример:
INPUT.TXT
5 7
1 2 1
1 3 3
1 4 2
2 3 1
3 4 1
4 5 1
3 5 4

OUTPUT.TXT
5
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.06.2013, 09:00     задача на систему дорог #2
bolabol, нужно все города посетить? Если да, то в примере должно получится 4: (1-2), (2-3), (3-4), (4-5) = 4.
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
02.06.2013, 09:36  [ТС]     задача на систему дорог #3
пример представляем в виде дерева. все соединено между собой:
5 7 (количество городов= 5, количество дорог= 7)
1 2 1(из города 1 в город 2 длина дороги= 1)
1 3 3(аналогично: из города 1 в город 3 длина дороги= 3) и т.д.
1 4 2
2 3 1
3 4 1
4 5 1
3 5 4
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.06.2013, 09:42     задача на систему дорог #4
bolabol, повторю вопрос:
Цитата Сообщение от Tulosba Посмотреть сообщение
нужно все города посетить?
и почему в примере результат 5, а не 4?
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
02.06.2013, 10:20  [ТС]     задача на систему дорог #5
Цитата Сообщение от Tulosba Посмотреть сообщение
bolabol, повторю вопрос:

и почему в примере результат 5, а не 4?
не знаю вообще, попробуйте программу написать с результатом= 4, плиз
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.06.2013, 10:27     задача на систему дорог #6
bolabol, Вы условие сформулируйте как следует, и пример приведите корректный. Потому что если Вам не понятно, что должна делать программа, никто другой ее не решит, или решит неправильно.
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
03.06.2013, 16:45  [ТС]     задача на систему дорог #7
Цитата Сообщение от Tulosba Посмотреть сообщение
bolabol, Вы условие сформулируйте как следует, и пример приведите корректный. Потому что если Вам не понятно, что должна делать программа, никто другой ее не решит, или решит неправильно.
Да и в правду, ошибочка вышла, не доглядел.
Вот правильная:

Система дорог
Даны N городов соединенных M дорогами. С любого города можно добраться до любого другого города. Из них оставить дороги, чтобы не осталось циклов и сумма длин оставшихся дорог была минимальна.
Входные данные
В первой строке заданы два целых числа N и M – количество городов и количество дорог. Со второй строки заданы номера городов соединенных дорогами и их длины.
Выходные данные
Напечатать одно число – суммарная длина

Пример:
INPUT.TXT
5 7
1 2 1
1 3 3
1 4 2
2 3 1
3 4 1
4 5 1
3 5 4

OUTPUT.TXT
4
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
03.06.2013, 16:50     задача на систему дорог #8
bolabol, вот решение алгоритмом Краскала с СНМ
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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int parent[20000],rank[20000];
void dsu_make(int v)
{
    parent[v]=v;
    rank[v]=0;
}
int dsu_find(int v)
{
    if (parent[v]==v)
        return v;
    return parent[v]=dsu_find(parent[v]);
}
void dsu_unite(int a,int b)
{
    a=dsu_find(a);
    b=dsu_find(b);
    if (a!=b)
    {
        if (rank[a]<rank[b])
            swap(a,b);
        parent[b]=a;
        if (rank[a]==rank[b])
            ++rank[a];
    }
}
int main()
{
    int n,m,i,a,b,w,k;
    scanf("%d%d",&n,&m);
    vector<pair<int,pair<int,int> > > g;
    for (i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&w);
        g.push_back(make_pair(w,make_pair(a-1,b-1)));
    }
    sort(g.begin(),g.end());
    for (i=0;i<n;i++)
        dsu_make(i);
    for (k=i=0;i<m;i++)
    {
        a=g[i].second.first;
        b=g[i].second.second;
        w=g[i].first;
        if (dsu_find(a)!=dsu_find(b))
        {
            k+=w;
            dsu_unite(a,b);
        }
    }
    printf("%d",k);
    return 0;
}
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
03.06.2013, 18:28  [ТС]     задача на систему дорог #9
Цитата Сообщение от aram_gyumri Посмотреть сообщение
bolabol, вот решение алгоритмом Краскала с СНМ
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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int parent[20000],rank[20000];
void dsu_make(int v)
{
    parent[v]=v;
    rank[v]=0;
}
int dsu_find(int v)
{
    if (parent[v]==v)
        return v;
    return parent[v]=dsu_find(parent[v]);
}
void dsu_unite(int a,int b)
{
    a=dsu_find(a);
    b=dsu_find(b);
    if (a!=b)
    {
        if (rank[a]<rank[b])
            swap(a,b);
        parent[b]=a;
        if (rank[a]==rank[b])
            ++rank[a];
    }
}
int main()
{
    int n,m,i,a,b,w,k;
    scanf("%d%d",&n,&m);
    vector<pair<int,pair<int,int> > > g;
    for (i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&w);
        g.push_back(make_pair(w,make_pair(a-1,b-1)));
    }
    sort(g.begin(),g.end());
    for (i=0;i<n;i++)
        dsu_make(i);
    for (k=i=0;i<m;i++)
    {
        a=g[i].second.first;
        b=g[i].second.second;
        w=g[i].first;
        if (dsu_find(a)!=dsu_find(b))
        {
            k+=w;
            dsu_unite(a,b);
        }
    }
    printf("%d",k);
    return 0;
}
хмм спасибо !
НО все же хотелось бы прогу по алгоритму на графах, ото это сложновато для меня. Крускал проходил, а СНМ не помню
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
03.06.2013, 20:25     задача на систему дорог #10
Цитата Сообщение от bolabol Посмотреть сообщение
НО все же хотелось бы прогу по алгоритму на графах
тут и используется алгоритм на графах, а СНМ он же DSU это только для ускорения работы, с ее помощью асимптотика из O(MlogN+N^2) превращается в O(MlogN)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2013, 17:31     задача на систему дорог
Еще ссылки по теме:

Нужно выявить ошибку (задача на систему массового обслуживания) C++
C++ Задача на двоичную систему
Определить есть ли в системе дорог город, куда можно попасть из любого другого, проезжая не более 100км C++

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

Или воспользуйтесь поиском по форуму:
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
05.06.2013, 17:31  [ТС]     задача на систему дорог #11
ошибки выдает, на rank ругается. и как туда добавить ресурсы input и output?

Добавлено через 14 часов 23 минуты
help люди

Добавлено через 22 часа 19 минут
Кто еще как решит эту "задачку" ?
Yandex
Объявления
05.06.2013, 17:31     задача на систему дорог
Ответ Создать тему
Опции темы

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