nerd's blog

...MATCHING...
By nerd, 13 years ago, In English

WELCOME To Everyone!!!

Recently I've learned MaxFlow, MinCostMaxFlow and Matching...

Where can I solve problems in matching?

Thanks...

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
why i'm getting minuses? because of my poor english?
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Try reading it http://codeforces.com/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.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply