#P6453. Zju1364 Machine Schedule
Zju1364 Machine Schedule
Zju1364 Machine Schedule
题目描述
有两台机器 A 和 B。机器 A 有 种工作模式,编号为 到 ;机器 B 有 种工作模式,编号为 到 。两台机器最初都处于模式 。
有 个任务。每个任务给出编号以及两个模式 ,可以选择由处于模式 的机器 A 完成,或由处于模式 的机器 B 完成。
每当一台机器切换到另一种工作模式时,需要重启这台机器一次;另一台机器的模式不变。可以自行安排任务的执行顺序。求完成全部任务最少需要重启机器多少次。处于初始模式 时就能完成的任务,无需为此重启。
输入格式
从标准输入读入多组测试用例。
每组第一行三个正整数 ,满足 ,。
接下来 行,每行三个整数 。其中 是任务编号, 是机器 A 可用于完成该任务的模式, 是机器 B 可用于完成该任务的模式,满足 、。任务编号不决定执行顺序。
输入以单独一行 结束,结束标志不属于任何测试用例。
输出格式
每组输出一行一个整数,表示最少重启次数。
样例输入
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
样例输出
3
样例说明
让机器 A 依次使用模式 ,共重启两次;机器 B 使用模式 ,重启一次。前八个任务可由机器 A 完成,最后两个任务可由机器 B 完成,总共重启三次。