2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Множество с максимальной мощностью.
Сообщение08.10.2013, 17:53 


26/08/11
120
Дана таблица $N \times M$, содержащая пустые и непустые клетки. Известны координаты непустых клеток. Найти множество непустых клеток максимальной мощности, такое что, любые два элемента этого множества (с индексами $i,j$) удовлетворяют всем условиям: $x_i \neq x_j , y_i \neq y_j , i \neq j$, где $x, y$ - координаты.
Есть ли какой-нибудь алгоритм сложности $O(NM)$ для решения этой задачи?

 Профиль  
                  
 
 Re: Множество с максимальной мощностью.
Сообщение08.10.2013, 20:00 
Заслуженный участник


04/05/09
4582
Классическая задача Bipartite matching - вариант Max flow.
В вашем случае быстрее, пожалуй, Hopcroft–Karp algorithm.

 Профиль  
                  
 
 Re: Множество с максимальной мощностью.
Сообщение08.10.2013, 20:06 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Погуглите "Максимальное паросочетание".

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group