HDU 1150 Machine Schedule

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1150

题意描述：

A和B两种机器有几种工作模式，而每种工作能在两种机器的不同模式下加工，每换一种工作模式需要重启一次，现在给出每种工作在每种机器下的工作模式，问最少需要重启多少次加工完工作。

解题思路：

主要难点在于建立二分图，求最少重启次数，也就是求最小点覆盖数，那么用匈牙利算法求出最大匹配数即可。

代码实现：

 1 #include<stdio.h>
 2 #include<string.h>
 3 int a,b,e[110][110],cx[110],cy[110],mk[220];
 4 int maxmatch();
 5 int path(int u);
 6 int main()
 7 {
 8     int t,t1,t2,t3;
 9     while(scanf("%d",&a), a != 0)
10     {
11         scanf("%d%d",&b,&t);
12         memset(e,0,sizeof(e));
13         while(t--)
14         {
15             scanf("%d%d%d",&t1,&t2,&t3);
16             if(t2 > 0 && t3 > 0) 
17             e[t2][t3]=1;
18         }
19         printf("%d
",maxmatch());
20     }
21     return 0;
22 } 
23 int maxmatch()
24 {
25     int i,res=0;
26     memset(cx,0,sizeof(cx));
27     memset(cy,0,sizeof(cy));
28     for(i=1;i<a;i++)
29     {
30         if(!cx[i])
31         {
32             memset(mk,0,sizeof(mk));
33             res += path(i);
34         }
35     }
36     return res;//返回返回值 
37 }
38 int path(int u)
39 {
40     int v;
41     //mk[u]=1;
42     for(v=1;v<b;v++)
43     {
44         if(e[u][v] && !mk[v])
45         {
46             mk[v]=1;
47             if(!cy[v] || path(cy[v]))//找已经配对过的对象找增广路 
48             {
49                 cx[u]=v;
50                 cy[v]=u;
51                 return 1;
52             }
53         }
54     }
55     return 0;
56 }