POJ 3189 Steady Cow Assignment

二分图多重匹配第二题，提前再说一句，二分图匹配用网络流均可解
因为受了ysk学长博客的影响，开始习惯用宏定义写代码，有点不习惯，搞得我在控制范围上浪费了一些时间。

题意：
n头牛，m个牛棚，每头牛各自有各自喜欢的牛棚，给出喜欢的牛棚顺序，每个牛棚容量，要求他们的喜欢范围最小。(就是所住牛棚的最大喜欢值 – 最小喜欢值 最小)

思路：
二分牛棚数 ，并枚举范围起点，判断可行性 这么暴力？

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#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 range(i, st, en) for (int(i) = (st); (st) <= (en); (st)++)
#define rrange(i, st, en) for (int(i) = (st); (st) >= (en); (st)--)
#define fill(ary, num) memset((ary), (num), sizeof((ary)))

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 30;
int n, m, maxcap;
bool vis[maxn];
int link[maxm][maxn], vlink[maxm], mat[maxn][maxm], num[maxm];

bool dfs(int u, int st)
{
    each(i, m) if (i >= st && i < maxcap + st)
    {
        int v = mat[u][i] - 1;
        if (vis[v])
            continue;
        vis[v] = true;
        if (vlink[v] < num[v]) {
            link[v][vlink[v]++] = u;
            return true;
        }
        each(j, vlink[v]) if (dfs(link[v][j], st))
        {
            link[v][j] = u;
            return true;
        }
    }
    return false;
}

bool hungary(int mid)
{
    maxcap = mid;
    each(st, m - mid + 1)
    {
        fill(vlink, 0);
        bool flag = true;
        each(i, n)
        {
            fill(vis, false);
            if (!dfs(i, st)) {
                flag = false;
                break;
            }
        }
        if (flag)
            return true;
    }
    return false;
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF) {
        each(i, n)
            each(j, m)
                scanf("%d", &mat[i][j]);
        each(i, m)
            scanf("%d", &num[i]);
        int l = 1, r = m, 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;
}