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

Максимальное паросочетание или что-то еще - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ RLE сжатие и формат BMP http://www.cyberforum.ru/cpp/thread848417.html
Здравствуйте, помогите найти программу, сжимающую bmp файлы с помощью встроенного в формат алгоритма RLE4 или RLE8. Стоит такая задача: нужно написать декомрессор bmp, реализующий использование...
C++ Компиляция MPI Доброго времени суток всем, даже не знаю где создать тему, но так как программа написана на с++ решил здесь. В общем вопрос следующий: как запустить MPI программу написанную для 6 процессоров на... http://www.cyberforum.ru/cpp/thread845647.html
C++ Создание TXT файла
Собственно есть длл при инжекте он делает txt файл с текстом(так на вин7), но на вин8 он не может создать, этот тхт файл на диске С. в чем может быть проблема? вот кодик ...
C++ Высчитывание оптимального размера буфера при копировании большого файла
Здравствуйте! Программа может копировать большие файлы(>4GB). Но немалую роль играет оптимизация самого процесса копирования. Думаю всем известно - при копировании больших файлов, файл "по кускам"...
C++ TDump аналог http://www.cyberforum.ru/cpp/thread844328.html
Всем КУ! Мне надо узнать, какие методы использует DLL. Нашёл TDump. Мне в ней всё понравилось, но она мне не выдала параметры к каждому методу, ну то есть какие аргументы использует функция. Есть...
C++ C++ и OpenGl урок NeHe Сделал по уроку Nehe 6 Куб прогружается но он белый а должна накладываться текстура вот код где загружаю текстуру GLvoid LoadGLTextures() { // Загрузка картинки AUX_RGBImageRec *texture1=... подробнее

Показать сообщение отдельно
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579

Максимальное паросочетание или что-то еще - C++

25.04.2013, 23:40. Просмотров 860. Ответов 0
Метки (Все метки)

Задача в следующем:
Есть двудольный граф, и в нем у каждой вершины степень не меньше 1. Нужно поудалять ребра из этого графа так, чтобы осталось минимальное множество ребер, и любая вершина первой доли была бы связана с какой-то вершиной второй доли (и обратно). Предлагается решение - искать максимальное паросочетание этого графа и выводить его мощность. Я не могу понять, каким макаром здесь прикручиваются паросочетания, ведь у нас может быть так, что из одной вершины будет выходить несколько ребер.
Плюс к этому есть еще вариант решения, видимо неверный - просто удалять, пока возможно, ребра, которые примыкают к вершинам, каждая из которых имеет степень больше чем 1.
Какой может быть контрпример к этому решению? И как здесь можно прикрутить задачу о поиске максимального паросочетания в двудольном графе?
Заранее спасибо за помощь и советы! :-)

PS: Это задача Timus 1109.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru