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

@newyork7776 · Регистрация: 21.05.2013

Author24 — интернет-сервис помощи студентам

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

Входные данные
Первая строка содержит количество вершин 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++

#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++

#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++

#include <algorithm>
void sort(const rebro &m)
{
sort("что-то здесь")
}

нужно отсортировать таким способом

Вернуться к обсуждению:
Сортировка рёбер по длине C++

Следующий ответ

Другие темы раздела
C++ классы и подклассы https://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. Для этого в нём должны быть реализованы следующие операции над строками. 1.Выполнение операции “больше” для двух строк. 2.Сокращение строки S на длину строки S1 слева. 3.Замена в строке всех прописных букв русского алфавита на строчные. 4.Замена в строке первых n...
C++ Секретарша https://www.cyberforum.ru/ cpp-beginners/ thread1003589.html Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям. В первой строке дано число N (1 ≤ N ≤ 1000) – количество личных дел. Далее для каждого из N учащихся следующие данные (каждое в своей строке): фамилия и имя, класс, дата рождения. Фамилия и имя – строки не более чем из 20 символов, класс – строка...	C++ Сортировка массива методом простого обмена https://www.cyberforum.ru/ cpp-beginners/ thread1003587.html Привет,программисты! Мне поставлена задача выполнить сортировку одномерного массива методом простого обмена. Массив я задаю с помощью датчика рандомных чисел. Мой датчик: #include<iostream.h> #include<stdlib.h> #include<conio.h> void main()
C++ С++ оператор присвоения Всем доброго времени суток. Я написал класс в котором имеется приватный указатель или вернее 2 мерный массив. Выглядит он вот так вот: class Bitmap { protected: Pixel** pixels = nullptr; Vector2 Size;	C++ Найти самое длинное слово https://www.cyberforum.ru/ cpp-beginners/ thread1003585.html Здравствуйте. Мне нужно найти самое длинное слово в предложении и его порядковый номер. Как сделать, чтоб ввод завершался с нажатием клавиши "Enter", а не нажиманием Ctrl+Z на новой строке, как сейчас. И можно ли вводить русский текст? #include <iostream> #include <string> #include <iterator> using namespace std; typedef istream_iterator< string> str_in_it;
C++ Подсчет количества вершин дерева на заданном уровне https://www.cyberforum.ru/ cpp-beginners/ thread1003551.html Напишите пожалуйста Проги для нахождения количества вершин для дерева на заданном уровне, и кто сможет помогите посчитать сложность алгоритма	C++ Подключение библиотек в MVS12E Здравствуйте, я начал изучать программирование на С++ OpenGL. Я нашел туториал, в котором написано, что нужно подключить библиотеки OpenGL32.lib GLu32.lib GLaux.lib Вот у меня возникает вопрос, где их взять и как их подключить? Я использую Microsoft Visual Studio 2012 Express буду благодарен, если вы мне поможете.
C++ Организация библиотеки Написал набор классов и функций для своего удобства, чтобы подключать их в любом проекте. Всего получилось 35 файлов. Поместил я эти файлы и деректорию Include моей студии. Когда в проекте подключаю файл и использую какую либо функцию, выпадает ошибка, ССылка на нерасрешенную лексему..... Исправляется все если я все эти файлы складываю в папку проекта и ВКЛЮЧАЮ их а сам проект. Что я не так... https://www.cyberforum.ru/ cpp-beginners/ thread1003526.html	C++ Абстрактные и производные классы С++ https://www.cyberforum.ru/ cpp-beginners/ thread1003517.html Проблема: Есть базовый класс "Фигура", и производные: "Точка", "Круг", "Прямоугольник", "Треугольник". Надо сделать чистую виртуальную функцию Transform, и переопределить её в производных классах. Принцип работы функции Transform: функция должна трансформировать точку в круг, круг в прямоугольник, прямоугольник в треугольник. Когда я пытался реализовать данную функцию то наткнулся на...
Ошибка с классом в C++ C++ #include <iostream> using namespace std; class Cat { public: Cat(int initAge); ~Cat(); void SetAge(int age); int GetAge(); private: int Age;	C++ Дружеские числа Два натуральных числа называют дружескими, если каждое с них будет равно сумме всех делителей другого, кроме этого самого числа. Найти все пары дружеских чисел, что находятся в диапазоне от 200 до 300 https://www.cyberforum.ru/ cpp-beginners/ thread1003482.html

	10.11.2013, 18:04