Подразделы

Другие разделы

Дата и время

13/03/2025 15:48:13

Авторизация

981. Schedule

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

There are many tasks which need to be done in order to construct a building. In order to perform these tasks, there should be a reasonable schedule. There might be relations between tasks. The difficulty we meet in creating a schedule is that the schedule has to satisfy all given relations among the given tasks.

Given a set of tasks and their relations, your task is to write a program to check whether it is possible to create a schedule to perform the tasks.

Input

The first line contains two integers

$n$ and

$k$ (

$1\ ≤\ n\ ≤\ 500$ ,

$0\ ≤\ k\ ≤\ 20000$ ), where

$n$ denotes the total number of tasks, and

$k$ denotes the total number of relations. The next

$k$ following lines describes

$k$ relations among the tasks. Let

$t_j$ be a starting time of the task

$j$ ,

$j\ =\ 1,\ 2,\ …,\ n$ . Each relation is one of the two forms:

$x\ y\ v$ means task $x$ must not start after task $y$ starts $v$ days, i.e. $t_x\ ≤\ t_y\ +\ v$ ,
$x\ y\ -v$ means task $x$ must not start before task $y$ starts $v$ days, i.e. $t_x\ ≥\ t_y\ +\ v$ ,

where

$v$ is positive integer not greater than

$10\ 000$ .

Output

Write "YES" if it is possible to construct a schedule to satisfy all the given relations among the given task, "NO" otherwise.

Sample Input 1

2 2
1 2 -2
1 2 1

Sample Output 1

NO

Sample Input 2

2 1
1 2 -1

Sample Output 2

YES

Источник: РГУ им. И.Канта, осенний командный турнир, 2007

03/07/2008	Лето 2008 дорешивание ( 6G)
14/07/2008	Лето 2008 - 6 (G)

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

981. Schedule

Schedule