Олимпиадный тренинг

Задача . Liars and Truth Tellers


Задача

Темы: графы

Среди N коров (2 <= N <= 1000) Фермера Джона некоторые всегда говорят правду, а некоторые всегда лгут.
ФД выслушал M утверждений (1 <= M <= 10,000) своих коров, каждое в форме "x y T", обозначающей, что корова x утверждает, что корова y всегда говорит правду или в форме "x y L", обозначающей, что корова x утверждает, что корова y всегда лжет.
Каждое утверждение вовлекает пару различных коров и одна и та же пара коров может появится во множестве утверждений.
К несчастью, не все записи утверждений были сделаны правильно. И теперь ФД хочет вычислить наибольшее A такое, что существует корректное распределение коровам статуса "лжеца" и "правдоруба", так, чтобы оказались корректными первые A высказываний из списка ФД.
PROBLEM NAME: truth
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M.
* Строки 2..1+M: Каждая строка в форме "x y L" или "x y T", описывающее утвеждение сделанное коровой x о корове y.
Формат выходных данных
* Строка 1: Максимальное значение A такое, что первые A утвеждений из списка могут ьыть корректны при определенном назначении N коровам статусов "лжец", "правдец".
Примечание
Утверждения 1 и 3 противоречивы всегда, а утверждения 1 и 2 могут быть непротиворечивы, если мы назначим коров 1..3 - "правдецами", а корову 4 - лжецом.
Примеры
№Входные данныеВыходные данные
1 
4 3
1 4 L
2 3 T
4 1 T
 
2
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет