#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define int long long
int head[100001], cur[100001], nxt[100001], wei[100001], to[100001], cnt = 2, level[100001], vis[100001], s,
                                                                     t;
const int inf = 0x3f3f3f3f;
void add(int u, int v, int w) {
    to[cnt] = v;
    wei[cnt] = w;
    nxt[cnt] = head[u];
    head[u] = cnt;
    cnt++;
    to[cnt] = u;
    wei[cnt] = 0;
    nxt[cnt] = head[v];
    head[v] = cnt;
    cnt++;
}
int bfs() {
    memset(level, -1, sizeof(level));
    memcpy(cur, head, sizeof(head));
    level[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int top = q.front();
        q.pop();

        for (int i = head[top]; i ; i = nxt[i]) {
            int tp = to[i];

            if (level[tp] == -1 && wei[i] > 0) {
                level[tp] = level[top] + 1;
                q.push(tp);
            }
        }
    }

    if (level[t] == -1)
        return 0;

    return 1;
}
int dfs(int now, int flow) {
    if (now == t)
        return flow;

    int remain = flow;

    for (int i = cur[now]; i ; i = nxt[i]) {
        cur[now] = i;
        int tp = to[i], w = wei[i];

        if (w > 0 && level[now] + 1 == level[tp]) {
            int c = dfs(tp, min(w, remain));
            remain -= c;
            wei[i] -= c;
            wei[i ^ 1] += c;
        }
    }

    return flow - remain;
}
int dinic() {
    int ans = 0;

    while (bfs()) {
        ans += dfs(s, inf);
    }

    return ans;
}
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int n1, n2, n3, m1, m2;
    cin >> n1 >> n2 >> n3 >> m1 >> m2;
    s = n1 + n2 + n2 + n3 + 1, t = s + 1;

    for (int i = 1; i <= n1; i++)
        add(s, i, 1);

    for (int i = 1; i <= m1; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v + n1, 1);
    }

    for (int i = 1; i <= n2; i++)
        add(i + n1, i + n1 + n2, 1);

    for (int i = 1; i <= m2; i++) {
        int u, v;
        cin >> u >> v;
        add(u + n1 + n2, v + n1 + n2 + n2, 1);
    }

    for (int i = 1; i <= n3; i++)
        add(i + n1 + n2 + n2, t, 1);

    cout << dinic();
    return 0;
}

三分图最大匹配的网络流解法

题目分析

本题要求求解三分图的最大匹配。三分图包含三个点集 $X, Y, Z$，边仅存在于 $X-Y$ 和 $Y-Z$ 之间（同点集内及 $X-Z$ 间无边）。一个匹配是由 $X$ 中一点 $i$、$Y$ 中一点 $j$、$Z$ 中一点 $k$ 组成的三元组 $\{i,j,k\}$，需满足 $i-j$ 和 $j-k$ 有边，且所有匹配的三元组无公共点。最大匹配即满足条件的三元组的最大数量。

核心思路：转化为最大流问题

三分图匹配问题可通过图论建模转化为最大流问题，利用最大流算法求解。关键思路是：
通过构造一个带源点和汇点的流网络，使网络的最大流值等于三分图的最大匹配数。具体建模如下：

1. 点集拆分与编号

为限制 $Y$ 中每个点仅被一个三元组使用，需将 $Y$ 中的每个点拆分为两个副本（记为 $Y_1$ 和 $Y_2$），通过两者间的边限制流量。各点在网络中的编号规则：

• $X$ 中点：编号 $1 \sim n_1$；
• $Y_1$（$Y$ 的第一个副本）：编号 $n_1+1 \sim n_1+n_2$；
• $Y_2$（$Y$ 的第二个副本）：编号 $n_1+n_2+1 \sim n_1+2n_2$；
• $Z$ 中点：编号 $n_1+2n_2+1 \sim n_1+2n_2+n_3$；
• 源点 $s$：编号 $n_1+2n_2+n_3+1$；
• 汇点 $t$：编号 $s+1$。

2. 边的构造

网络中边的容量均为 $1$（保证每个点仅被使用一次），具体如下：

• 源点 $s$ 到 $X$ 中每个点：表示 $X$ 中的点可参与匹配；
• $X$ 中点到 $Y_1$ 中对应点：若 $X$ 中的 $x_a$ 与 $Y$ 中的 $y_b$ 有边，则连 $x_a \to Y_1$ 中的 $y_b$；
• $Y_1$ 中每个点到对应 $Y_2$ 中同一点：限制 $Y$ 中的点仅被一个三元组使用；
• $Y_2$ 中每个点到 $Z$ 中对应点：若 $Y$ 中的 $y_a$ 与 $Z$ 中的 $z_b$ 有边，则连 $Y_2$ 中的 $y_a \to z_b$；
• $Z$ 中每个点到汇点 $t$：表示 $Z$ 中的点可参与匹配。

3. 最大流与最大匹配的关系

网络中从 $s$ 到 $t$ 的一条路径对应一个合法的三元组 $\{x, y, z\}$（路径为 $s \to x \to y_1 \to y_2 \to z \to t$）。由于所有边容量为 $1$，最大流值即为最多不相交的路径数，对应三分图的最大匹配数。

算法选择：Dinic 算法

求解最大流的高效算法有多种，本题选用 Dinic 算法，其优势在于：

• 时间复杂度为 $O(E \cdot V^2)$，其中 $V$ 为点数，$E$ 为边数；
• 对于本题规模（$n_1,n_2,n_3 \leq 1000$，总点数约 $4000$，边数约 $2 \times 5000 + 3 \times 1000 = 13000$），可高效求解。

代码解析

1. 网络流基础结构

// 邻接表存储边：head[u]为u的第一条边，to[cnt]为边的终点，wei[cnt]为容量，nxt[cnt]为下一条边
int head[100001], cur[100001], nxt[100001], wei[100001], to[100001], cnt = 2;
int level[100001]; // BFS分层结果
const int inf = 0x3f3f3f3f;

2. 加边函数

向网络中添加一条有向边 $u \to v$（容量 $w$）和反向边 $v \to u$（容量 $0$，用于残量网络）：

void add(int u, int v, int w) {
    to[cnt] = v;
    wei[cnt] = w;
    nxt[cnt] = head[u];
    head[u] = cnt;
    cnt++;
    to[cnt] = u;
    wei[cnt] = 0;
    nxt[cnt] = head[v];
    head[v] = cnt;
    cnt++;
}

3. Dinic 算法核心

• BFS 分层：计算从源点到各点的最短距离（层次），用于限制 DFS 搜索方向：

  int bfs() {
      memset(level, -1, sizeof(level));
      memcpy(cur, head, sizeof(head)); // 复制当前边指针（优化）
      level[s] = 0;
      queue<int> q;
      q.push(s);
      while (!q.empty()) {
          int top = q.front(); q.pop();
          for (int i = head[top]; i; i = nxt[i]) {
              int tp = to[i];
              if (level[tp] == -1 && wei[i] > 0) { // 仅访问有残量的边
                  level[tp] = level[top] + 1;
                  q.push(tp);
              }
          }
      }
      return level[t] != -1; // 若汇点可达，返回true
  }
  

• DFS 增广：在分层图中寻找增广路，更新残量网络：

  int dfs(int now, int flow) {
      if (now == t) return flow; // 到达汇点，返回当前流量
      int remain = flow;
      for (int i = cur[now]; i; i = nxt[i]) {
          cur[now] = i; // 更新当前边指针（避免重复访问）
          int tp = to[i], w = wei[i];
          if (w > 0 && level[now] + 1 == level[tp]) { // 仅沿层次递增方向搜索
              int c = dfs(tp, min(w, remain));
              remain -= c;
              wei[i] -= c; // 正向边减流量
              wei[i ^ 1] += c; // 反向边加流量（残量）
          }
      }
      return flow - remain; // 返回实际增广的流量
  }
  

• 最大流计算：反复调用 BFS 和 DFS，累加增广流量：

  int dinic() {
      int ans = 0;
      while (bfs()) {
          ans += dfs(s, inf);
      }
      return ans;
  }
  

4. 主函数（建图与求解）

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int n1, n2, n3, m1, m2;
    cin >> n1 >> n2 >> n3 >> m1 >> m2;
    
    // 定义源点s和汇点t
    s = n1 + n2 + n2 + n3 + 1, t = s + 1;
    
    // 1. 源点s到X的边（容量1）
    for (int i = 1; i <= n1; i++)
        add(s, i, 1);
    
    // 2. X到Y1的边（容量1，对应X-Y的边）
    for (int i = 1; i <= m1; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v + n1, 1); // Y1的编号为n1+1 ~ n1+n2
    }
    
    // 3. Y1到Y2的边（容量1，限制Y中每个点仅用一次）
    for (int i = 1; i <= n2; i++)
        add(i + n1, i + n1 + n2, 1); // Y2的编号为n1+n2+1 ~ n1+2n2
    
    // 4. Y2到Z的边（容量1，对应Y-Z的边）
    for (int i = 1; i <= m2; i++) {
        int u, v;
        cin >> u >> v;
        add(u + n1 + n2, v + n1 + n2 + n2, 1); // Z的编号为n1+2n2+1 ~ n1+2n2+n3
    }
    
    // 5. Z到汇点t的边（容量1）
    for (int i = 1; i <= n3; i++)
        add(i + n1 + n2 + n2, t, 1);
    
    // 计算最大流，即最大匹配数
    cout << dinic();
    return 0;
}

算法标签

• 网络流
• 最大流
• Dinic 算法
• 图论建模
• 三分图匹配

复杂度分析

• 点数 $V$：约 $n1 + 2n2 + n3 + 2 \approx 4000$（因 $n1,n2,n3 \leq 1000$）；
• 边数 $E$：约 $n1 + m1 + n2 + m2 + n3 \approx 13000$（因 $m1,m2 \leq 5000$）；
• 时间复杂度：$O(E \cdot V^2) \approx 13000 \times 4000^2 = 2.08 \times 10^{11}$，但 Dinic 算法在实际应用中（尤其单位容量网络）效率远高于理论值，可满足本题需求。

通过将三分图匹配转化为最大流问题，利用 Dinic 算法高效求解，成功得到最大匹配数。这种建模思路是图论中“匹配转流”的经典应用。