多重匹配

HDU 3605 Escape

Posted on

多重匹配模板题……也是从薛昊那偷来的题……

貌似有更好的做法……看到了什么二进制压缩什么的……

这题数据很大,时间卡的很紧,使得我对模板使用了解更深了一点。

题意:
地球上有n个人要移民,有m的星球可以提供移民,这些人都很挑剔,只去自己感兴趣的星球,问是否存在一个方案使得每个人都能去自己感兴趣的星球。
每个星球容纳人数有限。
人数1e5,星球数 10。

思路:
二分图多重匹配裸题。这里如果你对模板使用比较了解肯定是一发水过的……

这里要对数组强调一下。 记 左元数组 l ,右元数组 r

  • mat[n][m] 二维可达矩阵。
  • link[m][n] 二维连接矩阵,记录每个 r 元素 连接的 l 元素
  • vis[m] 单次dfs的访问记录数组
  • vlink[m] 记录每个 r 元素连接的 l 元素数量
  • num[m] 记录每个 r 元素的限制数量

简单说,只有可达矩阵是n开头的!!!!!!

靠着输入挂800+ms……

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#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); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 12;
const int inf = 0x3f3f3f3f;

int n, m;
int mat[maxn][maxm];
int link[maxm][maxn];
int vlink[maxm], vis[maxm], num[maxm];

inline bool scan_d(int& num)
{
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF)
        return false;
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else
        num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
    if (IsN)
        num = -num;
    return true;
}

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

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

int main()
{
    while (scanf("%d %d", &n, &m) != EOF) {
        each(i, n) each(j, m) scan_d(mat[i][j]);
        each(i, m) scan_d(num[i]);
        if (hungary())
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}
多重匹配

POJ 3189 Steady Cow Assignment

Posted on

二分图多重匹配第二题,提前再说一句,二分图匹配用网络流均可解
因为受了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;
}
多重匹配

POJ 2289 Jamie’s Contact Groups

Posted on

最近网络流有点写累了,就尝试着写了一下二分图。
这是我第一道二分图多重匹配的题目,基本上是看着模板敲的……
因为中间在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;
}