You are not logged in. Please login at www.codechef.com to post your questions!

×

COPRIME - Editorial

PROBLEM LINK:

Contest

DIFFICULTY:

HARD

PREREQUISITES:

Bipartite Graph
Maximum Bipartite Matching
Minimum Vertex Cover
Konig's Theorem

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).

CODE:

setter.cpp

RELATED PROBLEMS:

NWERC '08

This question is marked "community wiki".

asked 07 Feb '14, 03:18

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 12 Feb '14, 03:30

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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