二分图匹配

为了描述方便将两个集合分成左和右两个部分，所有匹配边都是横跨左右两个集合，可以假想成男女配对。

假设图有 $n$ 个顶点，$m$ 条边。

题目描述

给定一个二分图 $G$，即分左右两部分，各部分之间的点没有边连接，要求选出一些边，使得这些边没有公共顶点，且边的数量最大。

增广路算法

总复杂度为 $O(nm)$

P3386二分图最大匹配

// Luogu P3386 【模板】二分图最大匹配
// https://www.luogu.com.cn/problem/P3386 2024-03-26 19:13:38

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m, e;
constexpr int N = 1005;
int mat1[N], mat2[N], vis[N], ans;
vector<int> G[N];
bool dfs(int x) {
  for (auto it : G[x]) {
    if (not vis[it]) {
      vis[it] = true;
      if (mat2[it] == -1 or dfs(mat2[it])) {
        mat2[it] = x;
        mat1[x] = it;
        return true;
      }
    }
  }
  return false;
}
void solve() {
  cin >> n >> m >> e;
  for (int i = 0, x, y; i < e; i++) {
    cin >> x >> y;
    y += n;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  for (int i = 1; i <= n + m; i++) mat1[i] = mat2[i] = -1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n + m; j++) vis[j] = false;
    if (dfs(i)) ans++;
  }
  cout << ans << "\n";
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}

[ZJOI2009] 假期的宿舍

学校放假了……有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。

比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B 的床。而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。

我们已知一共有 $n$ 个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

第一行一个数 $T$ 表示数据组数。接下来 $T$ 组数据，每组数据第一行一个数 $n$ 表示涉及到的总人数。

接下来一行 $n$ 个数，第 $i$ 个数表示第 $i$ 个人是否是在校学生 ($0$ 表示不是，$1$ 表示是)。再接下来一行 $n$ 个数，第 $i$ 个数表示第 $i$ 个人是否回家 ($0$ 表示不回家，$1$ 表示回家，注意如果第 $i$ 个人不是在校学生，那么这个位置上的数是一个随机的数，你应该在读入以后忽略它)。

接下来 $n$ 行每行 $n$ 个数，第 $i$ 行第 $j$ 个数表示 $i$ 和 $j$ 是否认识 ($1$ 表示认识，$0$ 表示不认识，第 $i$ 行 $i$ 个的值为 $0$，但是显然自己还是可以睡自己的床)，认识的关系是相互的。

对于每组数据，如果存在一个方案则输出 ^_^，否则输出T_T。（注意输出的都是半角字符，即三个符号的 ASCII 码分别为 $94,84,95$）

对于 $30\%$ 的数据满足 $1 \le n \le 12$。

对于 $100\%$ 的数据满足 $1 \le n \le 50$，$1 \le T \le 20$。

CODE

// Luogu P2055 [ZJOI2009] 假期的宿舍
// https://www.luogu.com.cn/problem/P2055 2024-03-26 18:53:48

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
constexpr int N = 61;
int mat1[N], mat2[N], vis[N], sc[N], ho[N];
int st[N][N];
bool dfs(int x) {
  for (int i = 1; i <= n; i++) {
    if (!sc[i] or !st[x][i] or vis[i])
      continue;
    else {
      vis[i] = 1;
      if (mat2[i] == -1 or dfs(mat2[i])) {
        mat2[i] = x;
        mat1[x] = i;
        return true;
      }
    }
  }
  return false;
}
void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> sc[i];  // 0 非在校生 1 是在校生
  for (int i = 1; i <= n; i++) {
    cin >> ho[i];  // 0 不回家 1回家
    if (not sc[i]) ho[i] = 1;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) cin >> st[i][j];
  for (int i = 1; i <= n; i++) {
    if (sc[i]) st[i][i] = 1;
  }
  for (int i = 1; i <= n; i++) mat1[i] = mat2[i] = -1;
  for (int i = 1; i <= n; i++) {
    if (sc[i] and ho[i]) continue;
    for (int i = 1; i <= n; i++) vis[i] = false;
    if (not dfs(i)) {
      cout << "T_T\n";
      return;
    }
  }
  cout << "^_^\n";
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int __;
  cin >> __;
  while (__--) solve();
  return 0;
}