本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1375. 机器安排


Description

在某一个虚幻世界中,墨老师是一个工厂的负责人,现有两台机器A和B,A机器有\$0\sim n-1\$种工作模式,B机器有\$0~m-1\$种工作模式,初始时两台机器均在0工作模式。
现在有\$k\$项任务,任务可以以任意顺序被执行,每项任务都能在A机器或B机器的某个模式中完成,例如任务0可在A机器的模式3或B机器的模式4中完成,任务1可在A机器的模式2或B机器的模式4中完成,我们以\$(i,x,y)\$表示任务i可工作在A机器的\$x\$模式或B机器的\$y\$模式。
显然,要完成所有任务,我们需要时时变动机器的模式,请问如何才能使变动模式数最小?

Input

输入有多组测试数据,第一行包括三个整数\$n,m\$ (\$n,m,<100\$)和 \$k\$(\$k<1 000\$)。以下\$k\$行,每行三个参数 即\$i,x,y\$。最末一行以0结束。

Output

一个整数,即最小变动数。

Samples

Input Copy
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
Output
3

Source

算法宝典3 二分图
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags: dfs(1)
My history solutions

You didn't submit any solution!
Submit your solution

Login Register