poj1274 匈牙利算法二分图最大匹配

浏览数：18 / 时间：2015年06月08日

题意：有n个奶牛， m个畜舍，每个畜舍最多装1头牛，每只奶牛只有在自己喜欢的畜舍里才能产奶。求最大产奶量。

分析：其实题意很明显，二分图的最大匹配，匈牙利算法。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
using namespace std;

int n, m, sum, v[210], ans[210], map1[210][210];
int dfs(int x)//如果有增广路径返回1， 否则返回0
{
    for(int i = 1; i <= m; i++)
    {
        if(map1[x][i] == 1 && v[i] == 0)//有x-i边（牛x喜欢牛舍i） i没搜索过
        {
            v[i] = 1;
            //i是非匹配点，找到增广路径， 或者i是匹配点，从i继续往下找存在增广路径
            if(ans[i] == 0 || (ans[i] != 0 && dfs(ans[i]) == 1))
            {
                ans[i] = x;//记录牛舍i对应存放奶牛x
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(map1, 0, sizeof(map1));
        memset(ans, 0, sizeof(ans));
        int s, t;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &s);
            for(int j = 1; j <= s; j++)
            {
                scanf("%d", &t);
                map1[i][t] = 1;
            }
        }
        sum = 0;
        for(int i = 1; i <= n; i++)
        {
            //v标记是否是搜索过， 每一次查询都从新初始化所有v为0（为搜索过）
            memset(v, 0, sizeof(v));
            int t = dfs(i);
            if(t == 1)
                sum++;
        }
        printf("%d\n", sum);
    }
    return 0;
}