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

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

Войти
Регистрация
Восстановить пароль
 
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
#1

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

23.05.2013, 06:21. Просмотров 783. Ответов 10
Метки нет (Все метки)

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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2013, 06:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос задача на систему дорог (C++):

Задача на двоичную систему - C++
Необходимо вывести в консоль все положительные четырехзначные числа, в записи которых нет 7. Понимаю что скорее всего надо использовать...

задача на римскую систему счисления - C++
Ввести число римскими цифрами (менее 4000 в арабской записи), учитывая следующие обозначения: I - 1, V - 5, X - 10, L - 50, C - 100, D -...

Нужно выявить ошибку (задача на систему массового обслуживания) - C++
Дана такая задача: Проблема в сделанном коде в том, что программа выводит уж явно неверные значения для текущего и среднего кол-ва...

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

Минимизировать стоимость строительства дорог - C++
Нас толкоM не учили такоMу програMMированию, но препод дал такую задачку для решения: Три страны решили объединиться в союзное...

Количество построенных между городами дорог - C++
Древняя рукопись В некоторой древней стране жили-были братья. Сколько их было, нам точно не известно, но в исторических источниках...

10
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
02.06.2013, 09:00 #2
bolabol, нужно все города посетить? Если да, то в примере должно получится 4: (1-2), (2-3), (3-4), (4-5) = 4.
0
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
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
02.06.2013, 09:42 #4
bolabol, повторю вопрос:
Цитата Сообщение от Tulosba Посмотреть сообщение
нужно все города посетить?
и почему в примере результат 5, а не 4?
0
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
02.06.2013, 10:20  [ТС] #5
Цитата Сообщение от Tulosba Посмотреть сообщение
bolabol, повторю вопрос:

и почему в примере результат 5, а не 4?
не знаю вообще, попробуйте программу написать с результатом= 4, плиз
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
02.06.2013, 10:27 #6
bolabol, Вы условие сформулируйте как следует, и пример приведите корректный. Потому что если Вам не понятно, что должна делать программа, никто другой ее не решит, или решит неправильно.
1
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
0
dr.curse
390 / 346 / 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;
}
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;
}
хмм спасибо !
НО все же хотелось бы прогу по алгоритму на графах, ото это сложновато для меня. Крускал проходил, а СНМ не помню
0
dr.curse
390 / 346 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
03.06.2013, 20:25 #10
Цитата Сообщение от bolabol Посмотреть сообщение
НО все же хотелось бы прогу по алгоритму на графах
тут и используется алгоритм на графах, а СНМ он же DSU это только для ускорения работы, с ее помощью асимптотика из O(MlogN+N^2) превращается в O(MlogN)
0
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
05.06.2013, 17:31  [ТС] #11
ошибки выдает, на rank ругается. и как туда добавить ресурсы input и output?

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

Добавлено через 22 часа 19 минут
Кто еще как решит эту "задачку" ?
0
05.06.2013, 17:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2013, 17:31
Привет! Вот еще темы с ответами:

перевод с pascal, система односторонних дорог - C++
Задана система односторонних дорог. Найти путь, соединяющий города A и B и не проходящий через заданное множество городов uses crt; ...

По карте дорог необходимо определить самый удалённый город. - C++
По заданной карте дорог необходимо определить самый удалённый город от заданного среди всех доступных из этого заданного по кратчайшему...

В системе двухсторонних дорог за проезд каждой дороги взимается некоторая пошлина. - C++
В системе двухсторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города А в город Б с минимальной...

Определить есть ли в системе дорог город, куда можно попасть из любого другого, проезжая не более 100км - C++
Всем привет.Помогите с программой: Задана система односторонних дорог. Определить, есть ли в ней город, куда можно попасть из любого...


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

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

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