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

C++

Войти
Регистрация
Восстановить пароль
 
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579
#1

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

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

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

PS: Это задача Timus 1109.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2013, 23:40     Максимальное паросочетание или что-то еще
Посмотрите здесь:

посоветуйте какую-то книгу или даже видео курс,ну или еще что-то, ну чтобы с самого начала ,с нуля объяснялось. - C++
ВСЕМ привет. В общем дело вот в чем: Серьёзно решил заняться изучением C++ ,до этого ничем подобным не занимался ,ну разве что HTML...

If vs. If else - миф или что-то еще? - C++
Кто - нибудь проверял утверждение что if ... else занимает меньше времени чем if... if... if ? Я сравнила два варианта одной и той же...

Предел int или что то еще ? - C++
Задание: Определить входит ли введенная цифра в заданное натуральное число. Вот что у меня получилось: #include <iostream.h> void...

Нужен ли хостинг или что то еще, для работы программ клиент-сервер(TCP/IP) на разных компьютерах? - C++
Нужен ли хостинг или что то еще, для работы программ клиент-сервер(TCP/IP) на разных компьютерах?

CFileDialog и кое-что еще - Visual C++
Здравствуйте, мне нужна помощь в использовании CFileDialog. Задача состоит в том, что когда диалог сразу открывается в текущей папке то там...

Что еще можно параллельно изучать вместе с С++? - C++
Сейчас изучаю С++ по Дейтелам. Собственно, насколько я понимаю, программист - это не только знание ЯП"ов. Что еще можно параллельно...

Conversion from 'size_t' to 'int' и еще кое-что - C++
cout << "Vvedite slovo: "; string word; cin >> word; char temp; int i; int j; for (j=0, i=word.size() -...

Кроме Round и Floor еще есть что? - C++
Добрый вечер! Есть в с++ еще что-нибудь для округления при вычислениях (не выводе) кроме вышеуказанных. ______(x,i) - где x - вещ....

Задумываюсь чтоб начать сразу с Qt(пока еще ни во что не углублялся). - C++
Здравствуйте. QT это бесплатная и кроссплатформенная библиотека. Потому имеет смысл на нее обращать внимание. Я не могу решиться -...

Программа на Ваше обозревание, что можно еще добавить? Тру критика - C++
Всех приветствую! Уважаемое сообщество КФ, я тут новичок, но хотел бы вступить в ваши ряды, возможно даже стать больше чем серой...

Максимальное или минимальное значение - C++
Вот я сталкивался с заданием вычесления из массива минимального или максимального значения. Ведь машина понимает что 3>2. Но какое число...

Что нужно еще сделать для комфортной работы пользователей с моей программой? - C++
Спасибо тем кто откликнулся;)))) Я на скорую руку написал программку вычисляющая определитель матрицы (3X3) я начинающий скажите что еще...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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