hdu1150 Machine Schedule 经典二分匹配题目

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1150

很经典的二分题目

就是求最小点覆盖集

二分图最小点覆盖集=最大匹配数

代码：

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cstdio>
 5 #define maxn 110
 6 using namespace std;
 7 int ans;
 8 int n;
 9 int m;
10 int k;
11 int vis_x[maxn];
12 int vis_y[maxn];
13 int cx[maxn],cy[maxn];
14 
15 int g[maxn][maxn];
16 int path(int u)
17 {
18    vis_x[u]=1;
19 
20    for(int v=1;v<=m;v++)
21    {
22     if(g[u][v]>0 && (!vis_y[v]))
23     {
24       vis_y[v]=1;
25       if(!cy[v]|| path(cy[v]))
26       {
27         cx[u]=v;
28         cy[v]=u;
29         return 1;
30       }
31     }
32    }
33    return 0;
34 }
35 void MaxMatch()
36 {
37   ans=0;
38   memset(cx,0,sizeof(cx));
39   memset(cy,0,sizeof(cy));
40   for(int i=1;i<=n;i++)
41   {
42     if(!cx[i])
43     {
44 
45        memset(vis_x,0,sizeof(vis_x));
46        memset(vis_y,0,sizeof(vis_y));
47 
48        ans+=path(i);
49     }
50   }
51 
52   return ;
53 }
54 int main()
55 {
56     while(scanf("%d",&n)!=EOF)
57     {
58        if(n==0) break;
59        scanf("%d%d",&m,&k);
60 
61        memset(g,0,sizeof(g));
62        int a,b,c;
63        for(int i=0;i<k;i++)
64        {
65            scanf("%d%d%d",&a,&b,&c);
66            g[b][c]=1;
67        }
68 
69        MaxMatch();
70        printf("%d
",ans);
71     }
72 }