1 /*HDU1150 最小顶点覆盖
点覆盖集即一个点集，使得所有边至少有一个端点在集合里。或者说是“点” 覆盖了所有“边”。
2 题目描述：有两台机器A和B以及N个需要运行的任务。每台机器有M种不同的模式，而每个任务都恰好在一台机器上运行。
3
4 如果它在机器A上运行，则机器A需要设置为模式xi,如果它在机器B上运行，则机器A需要设置为模式yi。
5
6 每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。
7
8 建图
9 最小顶点覆盖==最大匹配
10 */
11 #include <iostream>
12 #include <cmath>
13 #include <algorithm>
14 #include <string.h>
15 #include <stdio.h>
16 #include <set>
17 #include <stack>
18 #include <vector>
19 #define maxn 510
20 using namespace std;
21
22 vector<int> G[2*maxn];
23 int match[2*maxn];//记录点的对应项
24 bool visit[2*maxn];//记录点是否在增广路上
25
26 int n,m,k;
27 void read(){
28 int mx=max(n,m);
29 for(int i=1;i<=m;i++){
30 G[i].clear();
31 }
32 cin>>k;
33 for(int i=1;i<=k;i++){
34 int num,x,y;
35 scanf("%d%d%d",&num,&x,&y);
36 if (x && y){
37 G[x].push_back(y);
38 }
39 }
40 }
41 bool dfs(int s)//找到从s点出发的可增广路
42 {
43 for(int i=0;i<G[s].size();i++){
44 int v=G[s][i];
45 if (!visit[v]){
46 visit[v]=true;
47 if (match[v]==0 || dfs(match[v])){//说明v对应的项有增广路
48 match[v]=s;//修改v的对应项（即互斥点）是s
49 return true;
50 }
51 }
52 }
53 return false;
54 }
55
56 int hungary(){
57 int ans=0;
58 memset(match,0,sizeof(match));//清空匹配
59 for(int i=1;i<=n;i++){
60 memset(visit,0,sizeof(visit));//注意清空增广路
61 if (dfs(i)) ans++;
62 }
63 return ans;
64 }
65
66 int main(){
67 while(cin>>n && n){
68 cin>>m;
69 read();
70 printf("%d
",hungary());
71 //最大匹配
72 }
73 return 0;
74 }