BZOJ5251 [多省联考2018] 劈配

2018 年 04 月 9 日发布.

Description

$n$ 个选手和 $m$ 个导师，第 $i$ 个选手把第 $j$ 个导师填到了自己的第 $a_{i,j}$ 志愿里。选手按照编号从小到大依次选择导师，每名选手会选择他所可能选到的最高志愿的老师之一（志愿编号越小就越高，如果 $a_{i,j}=0$ 表示第 $i$ 名选手未把第 $j$ 名导师填进志愿）。每名选手有一个目标值 $s_i$ 表示他想要选到第 $1~s_i$ 的志愿之一。

第 $i$ 名导师最多被选 $b_i$ 次。

问：每名选手会选到哪一个志愿、以及他要达成目标，最少要上升多少名次（在其它选手相对排名不变的情况下）。

$n, m\leqslant200$ ，每名选手每个志愿最多有 $10$ 名导师。

Solution

把选手看成 $X$ 结点，导师看成 $Y$ 结点。匈牙利算法。

“选择最高志愿”可以这样：当前枚举的选手从低到高选择志愿，之前已经选过某导师的选手只会选择与此导师的支援等级相同的导师。

匈牙利时如果某名导师被选的次数不到其上限，那么可以直接选上。否则枚举当前选它的所有选手 dfs 即可。

第二问...可以二分枚举答案然后跑一遍假的匈牙利（只找答案是否存在而不实际增广）就行了。

单次匈牙利复杂度是 $O( \text{边数} )$ 也就是 $O(nC+m)$ 的。一共要匈牙利 $O(n^2)$ 次（二分可以 $O(n\log n)$ 次不过不需要），总复杂度 $O(n^3C+n^2m)$ 。

Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>

typedef std::set<int> SI;
typedef std::vector<int> VI;

inline int readInt() {
  int ans = 0, c, f = 1;
  while (!isdigit(c = getchar())) if (c == '-') f *= -1;
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans * f;
}

const int N = 205;

int n, m;
int match[N], matchC[N];
int b[N], s[N], ans[N];
SI dui[N];
VI A[N][N];
bool visy[N];

bool dfs(int x, bool real = true) {
  int l = matchC[x] == 0 ? 1 : matchC[x];
  int r = matchC[x] == 0 ? m : matchC[x];
  for (int i = l; i <= r; ++i)
    for (VI::iterator it = A[x][i].begin(); it != A[x][i].end(); ++it) {
      int y = *it;
      if (visy[y]) continue;
      visy[y] = true;
      if (dui[y].size() < b[y]) {
        if (real) {
          match[x] = y;
          matchC[x] = i;
          dui[y].insert(x);
        }
        return true;
      }
      for (SI::iterator it2 = dui[y].begin(); it2 != dui[y].end(); ++it2)
        if (dfs(*it2, real)) {
          if (real) {
            dui[y].erase(it2);
            match[x] = y;
            matchC[x] = i;
            dui[y].insert(x);
          }
          return true;
        }
    }
  return false;
}

void init() {
  n = readInt();
  m = readInt();
  for (int i = 1; i <= m; ++i) {
    b[i] = readInt();
    dui[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    match[i] = matchC[i] = 0;
    ans[i] = 0;
    for (int j = 1; j <= m; ++j)
      A[i][j].clear();
    for (int j = 1; j <= m; ++j)
      A[i][readInt()].push_back(j);
  }
  for (int i = 1; i <= n; ++i)
    s[i] = readInt();
}

int main() {
  int T;
  scanf("%d%*d", &T);
  while (T--) {
    init();
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; ++j) {
        memset(visy, 0, sizeof visy);
        int tm = m; m = s[j];
        if (dfs(j, false)) ans[j] = i;
        m = tm;
      }
      memset(visy, 0, sizeof visy);
      dfs(i);
      printf("%d ", matchC[i] == 0 ? m + 1 : matchC[i]);
    }
    puts("");
    for (int i = 1; i <= n; ++i)
      printf("%d ", i - ans[i]);
    puts("");
  }
  return 0;
}