hdu1150 Machine Schedule

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<math.h>
 4 #include<string.h>
 5 #include<stdlib.h>
 6 using namespace std;
 7 const int N=110;
 8 int a[N][N];
 9 int use[N];
10 int match[N];
11 int n,m,k;
12 
13 int dfs(int u)
14 {
15     for(int i=0;i<m;i++)
16     {
17         if(a[u][i]==1 && !use[i])//判断是否联系和已匹配
18         {
19             use[i]=1;//标记匹配
20             if(match[i]==-1 || dfs(match[i]))//如果未匹配，进行匹配
21             {                                //如果已匹配，进行强制匹配本次，并回溯上一次已匹配的
22                 match[i]=u;                  //机器，对其进行其他匹配，如果不行，则本次匹配失败
23                 return 1;
24             }
25         }
26     }
27     return 0;
28 }
29 int bipartite()
30 {
31     int res=0;
32     memset(match,-1,sizeof(match));
33     for(int i=0;i<n;i++)
34     {
35         memset(use,0,sizeof(use));
36         if(dfs(i))
37         res++;
38     }
39     return res;
40 }
41 int main()
42 {
43     //freopen("in.txt","r",stdin);
44     while(~scanf("%d",&n))
45     {
46         if(!n)
47         break;
48         int h,p,q;
49         memset(a,0,sizeof(a));
50         scanf("%d%d",&m,&k);
51         for(int i=0;i<k;i++)
52         {
53             scanf("%d%d%d",&h,&p,&q);
54             if(p>0&&q>0)
55             a[p][q]=1;
56         }
57         int t=bipartite();
58         printf("%d\n",t);
59     }
60     return 0;
61 }