Блог пользователя svg_af

Coconuts and Minimum Cut ?
Автор svg_af, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

→ Ответить