HDU1150Machine Schedule（二分图最大匹配的DFS解法）

题目大意就是说有两台机器，分别有n，m种模式可以调节，有k个工作，某一个工作i可以在第一台机器的a[i]模式下或第二台机器的b[i]模式下工作，两台机器的初始模式为0，问如何分配这K件工作使得两台机器更换模式的次数最少。并难求最少次数。

这里有一个定理：

二分图的最少顶点覆盖 = 二分图的最大匹配

证明见http://hi.baidu.com/keeponac/item/111e3438988c786b7d034b56

感觉讲的不错，仔细看看，慢慢就会明白。

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define eps 1e-15
16 #define MAXN  105
17 #define INF 1000000007
18 #define MAX(a,b) (a > b ? a : b)
19 #define MIN(a,b) (a < b ? a : b)
20 #define mem(a) memset(a,0,sizeof(a))
21 #define mem_1(a) memset(a,-1,sizeof(a))
22 
23 bool vis[MAXN],Map[MAXN][MAXN];
24 int Left[MAXN],N,M,K;
25 
26 bool DFS(int u)
27 {
28     for(int v=0;v<M;v++) if(Map[u][v] && !vis[v])//连且通还没有用过
29     {
30         vis[v] = true;
31         if(Left[v]==-1 || DFS(Left[v]))//-1表示还没有匹配
32         {
33             Left[v] = u;//匹配
34             return true;
35         }
36     }
37     return false;//没有找到匹配的点，返回false
38 }
39 
40 int main()
41 {
42     while(~scanf("%d", &N) && N)
43     {
44         mem(Map); mem_1(Left);
45         scanf("%d%d", &M, &K);
46         int t,x,y,ans = 0;
47         for(int i=0;i<K;i++)
48         {
49             scanf("%d%d%d", &t, &x, &y);
50             if(x>0 && y>0)Map[x][y] = true;//由于状态初始化为0，所以不要考虑0
51         }
52         for(int i=0;i<N;i++)
53         {
54             mem(vis);//vis是为了防止右部查找到同一个点
55             if(DFS(i)) ans ++;
56         }
57         printf("%d
",ans);
58     }
59     return 0;
60 }