Menu
Article ACM

HDU 3605 Escape

NodeKey

NodeKey

• 2 min read

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

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

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

题意：
地球上有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;
}
Share