nerd's blog

...MATCHING...
By nerd, 15 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?
15 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it
why i'm getting minuses? because of my poor english?
→ Reply
15 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Try reading it http://mirror.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
15 years ago, hide # |
 
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
  • 15 years ago, hide # ^ |
     
    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