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

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

Восстановить пароль Регистрация
 
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
10.11.2013, 18:04     Сортировка рёбер по длине #1
Ориентированный взвешенный граф задан перечнем дуг (ориентированных рёбер). Отсортировать эти дуги по возрастанию длин, сохранив (в дополнительных полях) номера этих дуг во входных данных.

Входные данные
Первая строка содержит количество вершин 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("что-то здесь")
}
нужно отсортировать таким способом
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
10.11.2013, 22:30  [ТС]     Сортировка рёбер по длине #4
я не переписываю задание,я их нахожу и стараюсь сам решить(или посмотреть как правельно решать),сам изучаю с++ пытаюсь понять что-то.
Yandex
Объявления
10.11.2013, 22:30     Сортировка рёбер по длине
Ответ Создать тему
Опции темы

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