1274解题报告：

刚学了二分图就找了一个比较水的题练了一下，二分图的题比较固定，可以当做模板用，到时候改改输入就可以了，所以我把输入部分写成了函数到时候改输入部分也比较简单。

先说说1274 这道题，题意就是有n头牛到m个地方产奶，但是一些牛有自己爱去的产奶的地方，所以我们要写一个程序使这些牛最大化的到一个产奶屋产奶。（ps：一个屋只能容纳一头牛产奶）

下面是我的代码：

#include <stdio.h>

#include <string.h>

int search(int a);

void shuru(int a);

int n, m, map[201][201], link[201], used[201], count;

int main()

{   int i;

    while (scanf("%d%d", &n, &m) == 2) {

        count = 0;

        memset(map, 0, sizeof(map));                   //map[i][j]=1则表示从i能够走到j

        memset(link, -1, sizeof(link));                 //link[i]表示于第i个产奶屋相连的奶牛的序号

        shuru(n);

        for (i = 1; i <= n; i++)                        //匈牙利算法核心代码

        {

            memset(used, 0, sizeof(used));              //每次对循环中的used进行初始化，以确定该次是否遍历过某点

            if (search(i)!=0)                           //count变量计数，初值为0，每找到一个增广序列就增加1

                count++;

        }

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

    }

    return 0;

}

 

int search(int a)                                         //判断是否能构成新的增广序列的函数

{                                    

    int j;

    for (j = 1; j <= m; j++)                             //判断是否能连通和该次遍历中有没有被用过

 {

        if (map[a][j] == 1 && used[j] == 0)

        {                   

            used[j] = 1;                                 //标记用过此点

           if (link[j] == -1 || search(link[j])!=0)

              {                                            //判断是否有奶牛与之配对或是否能构成增广序列，匈牙利算法核心递

                link[j] = a;                             //录该j产奶屋对应的奶牛序号a

                return 1;

            }

        }

    }

    return 0;

}

void shuru(int a)                                         //输入函数

{   int s1,s2,i,j;

  for (i = 1; i <= a; i++)

  {

            scanf("%d", &s1);

            for (j = 1; j <= s1; j++)

              {

                scanf("%d", &s2);

                map[i][s2] = 1;

            }

       }

}