ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Zhupanenko                    2:4626/12.34   11 Jul 2001  12:49:26
 To : All
 Subject : Помогите решить
 -------------------------------------------------------------------------------- 
 

 
 Вот такая вот задачка:
 
 Есть матрица A (m x n) (m,n<=1024), елементы которой принимают
 значения 0 или 1. Каждая строчка матрицы A имеет свою цену.
 Матрица A удовлетворяет условиям:
 1. В каждой строке есть хотябы одна единичка.
 2. В каждом столбике есть хотябы одна единичка.
 
 Множество строчек M={x1,x2,...,xl}, (l<=m, xi- номер строки) будет
 тупиковым, если в каждом столбике матрицы B, составленой и множества
 строчек M будет хотябы одна единичка (проще говоря, если наложить все
 строчки друг на друга, в получившейся строчке не будет нулей).
 
 Hайти тупиковое множество M с минимальной ценой.
 
 Пример
 A:          Цены строк
 0 0 0 1 1   3                   +
 1 1 0 0 0   5                   -
 0 1 0 1 0   2                   +
 1 0 1 0 0   3                   +
 
 Множество M={1,3,4}
 
 Заранее благодарен.
 
 С уважением, Андрей Жупаненко.
 
  [Dead Kennedys]  [Выпуск 2000]  [VT dept]  [Лицей No 1]  [Punk's not dead]
  fido: 2:4626/12.34 e-mail: zhupanen@chv.ukrpack.net   phone: (03722)3-63-14
        2:463/4321.1         zhupanenko@svitonline.com         (044)476-84-46
 --- GoldEd 3.00.Beta3+
  * Origin: The Sun is Gone , but I Have a Light ... Kurt Cobain. (2:4626/12.34)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор