Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

A hard problem about graph theory(?)

Revision en4, by 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, x u + 1 = x v. There are another p ( p ≤ 100000) restriction, each restriction has form uv, meaning that if both factory u and v is built, x u ≤ x v. ( x i 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.

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)