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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ классы и подклассы http://www.cyberforum.ru/cpp-beginners/thread1003617.html
#include <iostream.h> #include <string.h> class Otdel_kadrov { public: char family; char inicialy; float oklad; float god_rozhd;
C++ Класс строка и переопределение операций Класс Строка должен включать данное типа строка символов - S и уметь обрабатывать параметр методов типа строка символов - S1. Для этого в нём должны быть реализованы следующие операции над строками.... http://www.cyberforum.ru/cpp-beginners/thread1003598.html
Секретарша C++
Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям. В первой строке дано число N (1 ≤ N ≤ 1000) –...
Сортировка массива методом простого обмена C++
Привет,программисты! Мне поставлена задача выполнить сортировку одномерного массива методом простого обмена. Массив я задаю с помощью датчика рандомных чисел. Мой датчик: ...
C++ С++ оператор присвоения http://www.cyberforum.ru/cpp-beginners/thread1003586.html
Всем доброго времени суток. Я написал класс в котором имеется приватный указатель или вернее 2 мерный массив. Выглядит он вот так вот: class Bitmap { protected: ...
C++ Найти самое длинное слово Здравствуйте. Мне нужно найти самое длинное слово в предложении и его порядковый номер. Как сделать, чтоб ввод завершался с нажатием клавиши "Enter", а не нажиманием Ctrl+Z на новой строке, как... подробнее

Показать сообщение отдельно
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,312
Завершенные тесты: 1

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

10.11.2013, 18:04. Просмотров 262. Ответов 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("что-то здесь")
}
нужно отсортировать таким способом
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.