hdu-1179 Ollivanders: Makers of Fine Wands since 382 BC.---二分图匹配模板

题目链接：

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

题目大意：

有n个人要去买魔杖，有m根魔杖（和哈利波特去买魔杖的时候一样，是由魔杖选人）。接下来是m行，每行第一个数k是第i根魔杖可以选的人数，接着k个数表示这根魔杖选的人的编号。最后问老板最多能卖出多少根魔杖。这个赤裸裸的模版题，套下就OK了。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF = 1e9;

 bool Map[maxn][maxn];

 int cx[maxn], cy[maxn];

 int cntx, cnty;

 bool vis[maxn];

 bool dfs(int u)

 {

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

     {

         if(Map[u][v] && !vis[v])

         {

             vis[v] = ;

             if(cy[v] == - || dfs(cy[v]))

             {

                 cx[u] = v;

                 cy[v] = u;

                 return ;

             }

         }

     }

     return ;

 }

 int maxmatch()

 {

     int ans = ;

     memset(cx, -, sizeof(cx));

     memset(cy, -, sizeof(cy));

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

     {

         if(cx[i] == -)

         {

             memset(vis, , sizeof(vis));

             ans += dfs(i);

         }

     }

     return ans;

 }

 int main()

 {

     int n, i, u, v;

     while(cin >> cnty && cnty)

     {

         cin >> cntx;

         memset(Map, , sizeof(Map));

         for(int u = ; u <= cntx; u++)

         {

             cin >> i;

             while(i--)

             {

                 cin >> v;

                 Map[u][v] = ;

             }

         }

         cout<<maxmatch()<<endl;

     }

     return ;

 }