A hard problem about graph theory(?)

Revision en1, by xuanquang1999, 2017-05-30 16:33:26

This is a problem I was given back when I'm training for APIO Vietnam team selection.

"There are n factory that is planned to be built on a line, number from 1 to n. There are m restriction, each restriction has form uv, meaning that if both factory u and v is built, xu + 1 = xv. There are another p restriction, each restriction has form uv, meaning that if both factory u and v is built, xu ≤ xv. (xi mean coordinate of factory i, if it's going to be built)

Your task is to choose a set of factories to build, and pick an appropriate coordinate for each factory, such that no restriction is violated, and the number of built factories is maximum."

I didn't understand the solution to this problem well back then. And now I'm trying to solve this again, but I can't think of any good idea. Can anyone give me a hint? Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English xuanquang1999 2017-05-31 18:44:08 2 Tiny change: 'actory".\n**UDP2**' -> 'actory".\n\n**UDP2**'
en4 English xuanquang1999 2017-05-31 18:43:33 304
en3 English xuanquang1999 2017-05-31 10:23:27 137
en2 English xuanquang1999 2017-05-30 17:07:01 51
en1 English xuanquang1999 2017-05-30 16:33:26 922 Initial revision (published)