POJ 2289 Jamie's Contact Groups

最近网络流有点写累了，就尝试着写了一下二分图。
这是我第一道二分图多重匹配的题目，基本上是看着模板敲的……
因为中间在main函数内外都定义了n,m ，搞得我debug了好久……

二分图多重匹配想比喻二分图单匹配来说，只是多加了几步，本质上还是一样的。基本上看代码就能看懂。

题意：
有个女神的备胎很多，每次找备胎都很麻烦，搞得她很困扰。现在女神想把他的备胎们分成m组，根据关系有的必须放在特别的组，但是女神数学不好，于是女神随手找了个备胎帮助计算，在满足条件的情况下有个组内人数max，现在要你求最小的max。

思路：
二分人数+多重匹配。
最大流也可。二分到汇点的容量即可。

这里有个小麻烦，就是有不定数量的数字。
一般人会立马想到，最麻烦的getchar() , 好一点的想到 stringstream
这里比较合适的应该是 一起输入一个数字和字符，如果字符是换行符号则退出。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define fill(ary, num) memset((ary), (num), sizeof((ary)))

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int n, m, maxcap;
bool vis[maxn], g[maxn][maxn];
int link[maxn][maxn], vlink[maxn];
char buf[60];

bool dfs(int u)
{
    each(i, m) if (g[u][i] && !vis[i])
    {
        vis[i] = true;
        if (vlink[i] < maxcap) {
            link[i][vlink[i]++] = u;
            return true;
        }
        each(j, vlink[i]) if (dfs(link[i][j]))
        {
            link[i][j] = u;
            return true;
        }
    }
    return false;
}

bool hungary(int mid)
{
    maxcap = mid;
    fill(vlink, 0);
    each(i, n)
    {
        fill(vis, false);
        if (!dfs(i))
            return false;
    }
    return true;
}

inline void input(int u)
{
    int a;
    char c;
    scanf("%s", buf);
    while (true) {
        scanf("%d%c", &a, &c);
        g[u][a] = true;
        if (c == '\n')
            break;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while (scanf("%d %d", &n, &m) != EOF && (n || m)) {
        fill(g, false);
        each(i, n) input(i);
        int l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (hungary(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        printf("%d\n", r + 1);
    }
    return 0;
}