hdu1150 Machine Schedule 经典二分匹配题目

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

很经典的二分题目

就是求最小点覆盖集

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

代码：

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<cstdio>

 #define maxn 110

 using namespace std;

 int ans;

 int n;

 int m;

 int k;

 int vis_x[maxn];

 int vis_y[maxn];

 int cx[maxn],cy[maxn];

 int g[maxn][maxn];

 int path(int u)

 {

    vis_x[u]=;

    for(int v=;v<=m;v++)

    {

     if(g[u][v]> && (!vis_y[v]))

     {

       vis_y[v]=;

       if(!cy[v]|| path(cy[v]))

       {

         cx[u]=v;

         cy[v]=u;

         return ;

       }

     }

    }

    return ;

 }

 void MaxMatch()

 {

   ans=;

   memset(cx,,sizeof(cx));

   memset(cy,,sizeof(cy));

   for(int i=;i<=n;i++)

   {

     if(!cx[i])

     {

        memset(vis_x,,sizeof(vis_x));

        memset(vis_y,,sizeof(vis_y));

        ans+=path(i);

     }

   }

   return ;

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

        if(n==) break;

        scanf("%d%d",&m,&k);

        memset(g,,sizeof(g));

        int a,b,c;

        for(int i=;i<k;i++)

        {

            scanf("%d%d%d",&a,&b,&c);

            g[b][c]=;

        }

        MaxMatch();

        printf("%d\n",ans);

     }

 }