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

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

Войти
Регистрация
Восстановить пароль
 
newyork7776
 Аватар для newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
#1

Сортировка рёбер по длине - C++

10.11.2013, 18:04. Просмотров 222. Ответов 3
Метки нет (Все метки)

Ориентированный взвешенный граф задан перечнем дуг (ориентированных рёбер). Отсортировать эти дуги по возрастанию длин, сохранив (в дополнительных полях) номера этих дуг во входных данных.

Входные данные
Первая строка содержит количество вершин N ( 2 ≤ N ≤ 30000 ) и количество дуг (ориентированных рёбер) M ( 1 ≤ M ≤ 123456 ). Каждая из последующих M строк содержит ровно три целых числа u , v и len — начало, конец и длину дуги. 1 ≤ u , v ≤ N , u ≠ v , 1 ≤ len ≤ 10 9 . Гарантированно, что дл и ны всех дуг различны.

Выходные данные
Результат должен содержать M строк по четыре целых числа u , v , len , idx в каждой — начало, конец, длину дуг и , и её номер во входных данных (нумерация с единицы). При этом д у ги должны быть отсортированы по возрастанию длин.

Примеры
входные данные
3 4
3 2 4
3 1 8
1 2 14
1 3 2
выходные данные
1 3 2 4
3 2 4 1
3 1 8 2
1 2 14 3

вот мои наброски
Кликните здесь для просмотра всего текста
сначала было дело так
Кликните здесь для просмотра всего текста
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
63
64
65
66
#include <iostream>
#include <cstdlib>
#include <cstring>
 
using namespace std;
 
struct rebro
{
    int one;
    int two;
    int tree;
    int four;
};
 
void print(const rebro &m)
{
    cout << m.one << " " << m.two << " " << m.tree << " " << m.four+1 << "\n";
}
 
void init(rebro &m)
{
    cout << "u: ";
    cin >> m.one;
    cout << "v: ";
    cin >> m.two;
    cout << "len: ";
    cin >> m.tree;
}
void mySort(rebro *arr, const int n)
{
    for(int i = 0; i < n - 1; ++i) 
    {            
        for(int j = 0; j < n - 1; ++j) 
            if (arr[j+1].four < arr[j].four)
            {
                rebro tmp = arr[j+1]; 
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
    }
}
 
 
int main()
{
    const int size = 3000;
    rebro pArr[size];
    int n,m;
    cout << "Enter number N = ";cin >> n;
    cout << "Enter number M = ";cin >> n;
    for (int i=0; i < n; i++)
    {
        init(pArr[i]);
        pArr[i].four=i;
    }
 
    for (int i=0; i < n; i++)
        print(pArr[i]); 
 
    cout << "\nSorted:\n";
    mySort(pArr, n);
    for (int i=0; i < n; i++)
        print(pArr[i]); 
 
    system("pause");
}

потом протризвел и понеслась
Кликните здесь для просмотра всего текста
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 <iostream>
#include <cstdlib>
#include <algorithm>
 
using namespace std;
 
struct rebro
{
    int one;
    int two;
    int tree;
    int four;
};
 
void print(const rebro &m)
{
    cout << m.one << " " << m.two << " " << m.tree << " " << m.four+1 << "\n";
}
 
int main()
{
    const int size = 3000;
    rebro pArr[size];
    int n,m;
    cout << "Enter number N = ";cin >> n;
    cout << "Enter number M = ";cin >> n;
    for (int i=0; i < n; i++)
    {
        cin << pArr[i].one << pArr[i].two << pArr[i].tree; 
        pArr[i].four=i;
    }
 
    for (int i=0; i < n; i++)
        print(pArr[i]); 
 
    cout << "\nSorted:\n";
 
    //sort algorithm по pArr[i].four от мин к макс
 
    for (int i=0; i < n; i++)
        print(pArr[i]); 
    system("pause");
}

а потом проблемка
C++
1
2
3
4
5
#include <algorithm>
void sort(const rebro &m)
{
sort("что-то здесь")
}
нужно отсортировать таким способом
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2013, 18:04     Сортировка рёбер по длине
Посмотрите здесь:

C++ Отсортировать слова по длине
Отсортировать слова по длине C++
Сортировка строк по длине первого слова C++
C++ Сортировка строки по длине слова
C++ Преобразовать список рёбер в список смежностей
Поиск вектора, минимального по длине C++
C++ Сортировка слов по их длине
Сортировка по длине C++
Ориентированный граф. Получить из списка рёбер матрицу смежности C++
C++ Проверить, является ли ориентированный граф, с заданным количеством узлов и рёбер, деревом
Сортировка слов в строке по длине слова C++
Вывести большую по длине строку C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1886 / 1741 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
10.11.2013, 18:29     Сортировка рёбер по длине #2
А ты и дальше будешь сюда олимпиадные задачки из асмп (или откуда там) перепечатывать?
Какой смысл?
Jupiter
10.11.2013, 18:32
  #3

Не по теме:

Цитата Сообщение от newyork7776 Посмотреть сообщение
потом протризвел
Цитата Сообщение от newyork7776 Посмотреть сообщение
а потом проблемка
C++
1
2
3
4
5
#include <algorithm>
void sort(const rebro &m)
{
sort("что-то здесь")
}
ты пьян иди домой

newyork7776
 Аватар для newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
10.11.2013, 22:30  [ТС]     Сортировка рёбер по длине #4
я не переписываю задание,я их нахожу и стараюсь сам решить(или посмотреть как правельно решать),сам изучаю с++ пытаюсь понять что-то.
Yandex
Объявления
10.11.2013, 22:30     Сортировка рёбер по длине
Ответ Создать тему
Опции темы

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