×

Contest

HARD

# EXPLANATION:

Problem boils down to:

Given a bipartite graph with directed edges, do matching to maximise the edges, but each vertex should either have all incoming or all outgoing edges (not both).

We can solve this problem by making a new bipartite graph, where, vertices on left side in new graph denote the directed edges from left to right in original graph. Vertices on right side in new graph denote the directed edges from right to left in original graph.

In the new graph, edges will be between those vertices which contradict each other. Two vertices contradict each other when both cannot exist in the final matching of the original graph. We need to remove minimum vertices in the new graph such that all contradictions (ie. edges in new graph) are removed.

This is same a minimum vertex cover, which is same as maximum bipartite matching (according to Konig's Theorem).

setter.cpp

# RELATED PROBLEMS:

NWERC '08

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,343
×1,218
×86
×9

question asked: 07 Feb '14, 03:18

question was seen: 2,716 times

last updated: 12 Feb '14, 03:30