poj 1274 The Perfect Stall 解题报告

题目链接：http://poj.org/problem?id=1274

题目意思：有 n 头牛，m个stall，每头牛有它钟爱的一些stall，也就是几头牛有可能会钟爱同一个stall，问牛与 stall 最大匹配数是多少。

二分图匹配，匈牙利算法入门题，留个纪念吧。

书上看到的一些比较有用的知识点：

增广：通俗地说，设当前二分图中，已有 x 个匹配边（也就是假设代码中match[i] 不为0的个数有x个），现在对 i 点（也就是代码中dfs中的参数 x） 指定一个匹配点 j， 由于 j 可能有匹配点设为 k（map[x][i]），必须要为k找到一个新匹配 （对应黑屏中的前两次增广，本来的match[2] 从 1 变为 2 了，因为要为牛2找stall ，遇到map[2][2]边的时候发现match[2] 有数，只能调用dfs(match[2]) 为 match[2]找另一个匹配，也就是map[1][5]，发现能找到，于是match[5] = 1，match[2] 就顺利成章变为2了）。

若能够找到，则表示匹配成功了x + 1 条边；若不能找到，相当于还是只有 x 个匹配边，只不过换了一种匹配方案而已，若达不到增加一条边的目的则称为对 i 增广不成功。

 #include <iostream>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring> using namespace std;
 const int maxn =  + ; int map[maxn][maxn];
 int match[maxn];   // match[m]存储了匹配的方案, match[i] = j　：仓库i里是牛j
 bool vis[maxn];
 int n, m, cnt; int dfs(int x)  // 深搜找增广路径
 {
     for (int i = ; i <= m; i++)
     {
         if (!vis[i] && map[x][i])  // 对x的每个邻接点
         {
             vis[i] = true;
             if (match[i] ==  || dfs(match[i]))  // 若 match[i] 点是一个初始值，表示i点原来没有匹配，则增广成功返回
             {                                     // 或者 match[i]点能重新找到一个新的匹配点
                 match[i] = x;                 // 保证新的匹配方案
                 return ;
             }
         }
     }
     return ;
 } void Hungary()
 {
     cnt = ;
     for (int i = ; i <= n; i++)  // 对 n 个点依次进行增广
     {
         memset(vis, , sizeof(vis));
         cnt += dfs(i);    // 增广成功，表示i点找到了一个匹配，多了一条匹配边
     }
 } int main()
 {
     int k, to;   // k: stall_num， to：stall_id
     while (scanf("%d%d", &n, &m) != EOF)
     {
         memset(map, , sizeof(map));
         memset(match, , sizeof(match));         for (int i = ; i <= n; i++)
         {
             scanf("%d", &k);
             for (int j = ; j <= k; j++)
             {
                 scanf("%d", &to);
                 map[i][to] = ;
             }
         }
         Hungary();
         printf("%d\n", cnt);
     }
 }