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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ RLE сжатие и формат BMP http://www.cyberforum.ru/cpp/thread848417.html
Здравствуйте, помогите найти программу, сжимающую bmp файлы с помощью встроенного в формат алгоритма RLE4 или RLE8. Стоит такая задача: нужно написать декомрессор bmp, реализующий использование цветовой палитры, RLE сжатия и проч. Проблема возникла при отладке декомпрессора, как оказалось, RLE-сжатие в bmp используется очень редко, потому-что единственным положительным качеством bmp-изображений...
C++ Компиляция MPI Доброго времени суток всем, даже не знаю где создать тему, но так как программа написана на с++ решил здесь. В общем вопрос следующий: как запустить MPI программу написанную для 6 процессоров на одном ядре, если допустим всего их два, то есть чтоб шести потокам было доступно одно ядро, независимо от их количества, возможно ли такое? http://www.cyberforum.ru/cpp/thread845647.html
C++ Создание TXT файла
Собственно есть длл при инжекте он делает txt файл с текстом(так на вин7), но на вин8 он не может создать, этот тхт файл на диске С. в чем может быть проблема? вот кодик strcpy(Base.dllpath,Base.dllpath); strcpy(Base.logfile,Base.GetFile("C:\\WMID.txt")); Base.LOG = fopen(Base.logfile,"w"); Base.WriteFile(Base.LOG,Asss); void __fastcall cBase::WriteFile(FILE *file,const char *fmt, ...)...
C++ Высчитывание оптимального размера буфера при копировании большого файла
Здравствуйте! Программа может копировать большие файлы(>4GB). Но немалую роль играет оптимизация самого процесса копирования. Думаю всем известно - при копировании больших файлов, файл "по кускам" копируется в другой файл, а размер "куска" определяется буфером, который используется. Я сделал множество тестов, проверяя зависимость размера буфера от скорости копирования(меняя каждый раз размер) и...
C++ TDump аналог http://www.cyberforum.ru/cpp/thread844328.html
Всем КУ! Мне надо узнать, какие методы использует DLL. Нашёл TDump. Мне в ней всё понравилось, но она мне не выдала параметры к каждому методу, ну то есть какие аргументы использует функция. Есть ли её аналог, который вместе с названием функции показывает и аргументы с их типами??? Или есть ещё какие нибуть способы узнать что надо определённой функции???
C++ C++ и OpenGl урок NeHe Сделал по уроку Nehe 6 Куб прогружается но он белый а должна накладываться текстура вот код где загружаю текстуру GLvoid LoadGLTextures() { // Загрузка картинки AUX_RGBImageRec *texture1= auxDIBImageLoadA("Data\NeHe.bmp"); glGenTextures(1, &texture); glBindTexture(GL_TEXTURE_2D, texture); glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_LINEAR); подробнее

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

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

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

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

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