Имя: Пароль: Зарегистрироваться Восстановить пароль
10/12/2023 03:20:04

# Рабочее место участника

## Задачи

981. Schedule

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод Послать решение 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 