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

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

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

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

10.11.2013, 18:04. Просмотров 239. Ответов 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++
На вход подается некоторое количество векторов R2, векторов R3 и отрезков R3. Отсортировать и вывести их по возрастанию длин. Помогите,...

Сортировка слов по их длине - C++
Ввести строку. На печать выдать новую строку в которой все слова расположены в порядке возрастания длин слов.

Сортировка строки по длине слова - C++
Сабж. Здравствуйте. Есть код, который вроде логически построен правильно, но он не работает. Уже не знаю как быть. Подскажите пожалуйста в...

Сортировка слов в строке по длине слова - C++
Помогите пожалуйста с алгоритмом сортировки строки. Необходимо осуществить сортировку строки чтобы в начале строки располагалось слово...

Сортировка строк по длине первого слова - C++
Добрый вечер формучане.Облазил весь нет как и этот форум но толком ничего не нашел.Собственно обращаюсь с просьбой решить эту задачку....

Отсортировать слова по длине - C++
Здравствуйте, у меня есть задание с таким условием: &quot;Есть файл со словами. Вывести на экран все слова в которых количество гласных, стоящих...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 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("что-то здесь")
}
ты пьян иди домой

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.11.2013, 22:30     Сортировка рёбер по длине
Еще ссылки по теме:

Отсортировать слова по длине - C++
Вот условие программы: &quot;Есть файл со словами. Вывести на экран все слова в которых количество гласных, стоящих на позициях с четными и...

Выравнивание строки s слева к длине m - C++
Выравнивание строки s слева к длине m. Left (s,m). C помощью функции.

Поиск вектора, минимального по длине - C++
Даны m векторов х1 = (х11, х21, ...,хn1), ..., xm = (x1m, x2m, ...,xnm). Написать программу поиска вектора минимального по длине. ...

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


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

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

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