svg_af's blog

Coconuts and Minimum Cut ?
By svg_af, history, 9 years ago, In English

Hello there

i came across this problem on spoj

we have 500 people where some believe a bird can carry a coconut and some don't (N<=500)

now each person has friends, and we want the sum of people who change what they think and the conflicts of opinions between friends to be minimum

i googled and found that it's a min cut problem ... but i failed to understand the reason

any explanation would be greatly appreciated

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Create a graph with a source s, a sink t and a node foreach person ui. If the person i believe in X add an edge from s to ui with capacity 1, if not add and edge from ui to t with capacity 1. Add edges (ui, uj) and (uj, ui) with capacity 1 if the person i and j are friends.. Let's look any distribution whose value is k, we can in our graph associate a cut with this capacity, how?? simple, took the persons who vote for X but does not believe it and add them to S, and the persons who believe in X but does not vote in favor and put them in T. is a cut with capacity k. Thus any cut is a distribution with value the capacity of the cut, we want to minimize the value of the distribution, that is equivalent to find a cut of minimum capacity among all cuts..

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you for excellent explanation ... i get it now

    → Reply