A hard problem about graph theory(?)

Правка en4, от xuanquang1999, 2017-05-31 18:43:33

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

"There are n (n ≤ 600) factory that is planned to be built on a line, number from 1 to n. There are m (m ≤ 100000) restriction, each restriction has form uv, meaning that if both factory u and v is built, xu + 1 = xv. There are another p (p ≤ 100000) 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 pick an appropriate coordinate for each factory, such that no restriction is violated, and the number of different coordinate is maximum. (If there's no way to do this, print "-1")

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.

UDP1: Sorry about the mistaken objective. The correct objective is "the number of distinct point", not "factory". UDP2: The problem I'm asking is the same with this POI problem (Thanks Swistakk for informing me this). I've updated the statement summary in the blog.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский xuanquang1999 2017-05-31 18:44:08 2 Tiny change: 'actory".\n**UDP2**' -> 'actory".\n\n**UDP2**'
en4 Английский xuanquang1999 2017-05-31 18:43:33 304
en3 Английский xuanquang1999 2017-05-31 10:23:27 137
en2 Английский xuanquang1999 2017-05-30 17:07:01 51
en1 Английский xuanquang1999 2017-05-30 16:33:26 922 Initial revision (published)