Блог пользователя nerd

...MATCHING...
Автор nerd, 13 лет назад, перевод, По-русски

Добро пожаловать всем!

Недавно я узнал, MaxFlow, MinCostMaxFlow и Matching...

Где я могу решать проблемы в соответствие?

Спасибо ...

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
why i'm getting minuses? because of my poor english?
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Try reading it http://codeforces.net/blog/entry/1279?locale=ru . The post similiar to yours (about max flow related problems - matchings, max flow, min cost and etc.). It's in russian, but you can find the links on problems, which are commonly in english.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=437&chapterid=588
As i understood, here we are given N cubes{with 6 letters on each side}  and name. We must answer, if we are able to gather name by using any letter from each cube?
If so, how can I use matching here?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    We build graph with two sets of vertecies: 1) cubics, 2) every letter of name. We add edge between cubic i and letter j of name if there are exist letter j on cubic i. Now we just find max matching in bipartite graph. If the size of matching is equal to length of the name, then answer is yes.
    → Ответить