深蓝黑背景封面：左侧大标题「配房间之前，先画一张二分图」，副标题「满意度最大化的建模与匈牙利算法思路」；右侧原创示意图——左侧三个游客圆点、右侧三个房间方块，中间若干连线表示「满意可选」，其中三条匹配线用亮色加粗；左上标注「面试经典 · 算法」，右上标注「Day 10 · 10-28」 图 1：本文封面，配房间之前先画图。

先说明属性：这是一篇历史题目复盘，题目出自本地历史面试资料，与任何公司的当前招聘无关。题面大意：若干游客和若干房间，每个游客只对部分房间满意，问怎么分配才能让住下的游客最多（或总满意度最高）。

先把结论立住：**这类分配问题的通用第一步不是写算法，而是建模——把两类对象放进左右两个集合，「可以搭配」画一条边，问题就变成在二分图上选一批互不相邻的边。建模对了，剩下的交给增广路。**匈牙利算法的全部直觉只有一句话：给新游客找房时，如果看中的房被占了，别直接放弃，问问「占着的人能不能挪」。

**建模这一步值一半的分。**游客与房间、任务与机器、标注员与工单，凡是「两边配对、一对一只能用一次」的问题都是同构的。边可以带权表示满意度，目标可以是匹配数最大（无权）或权值和最大（带权）。能把业务约束翻译成「边存在还是不存在」，问题就已经解了一半。

**增广路：匈牙利算法的心脏。**当前匹配里游客甲占着房间 A，给游客乙找房时发现 A 已被占。算法不问「还有没有空房」，而是问「甲能不能挪」：甲还能去还空着的房间 B，于是甲挪去 B、乙住进 A，匹配总数加一。这条「乙→A→甲→B」的换人链就是增广路。判据很整齐：从还没匹配的点出发，沿「非匹配边、匹配边」交替走，能走到一个空位就把路径上的边全部翻转，匹配数严格加一；找不到增广路时，当前匹配就是最大匹配。

建模加算法思路图：上方左侧是建模三步——把问题里的两类对象放进左右两个集合（游客与房间、任务与机器、标注员与工单），凡是「可以搭配」的就画一条边，边有权表示满意度，目标变成在图上选一批互不相邻的边使权值和最大。上方右侧是匈牙利算法的一步演示——当前匹配里游客甲占着房间 A，给游客乙找房时发现 A 已被占；算法不直接放弃，而是问「占着的人能不能挪」：让甲改去还空着的房间 B，乙住进 A，一条「换房链」走完，匹配总数加一，这条链就是增广路。下方提示增广路判据：从还没匹配的点出发，沿着「非匹配边、匹配边」交替走，若能走到一个空位，就把路径上的边全部翻转——翻转后匹配数严格加一，找不到增广路时当前匹配即最大。底部提示：二分图匹配的关键不是算法细节，而是先把分配问题抽象成左右两列点和可选边——建模对了，剩下的交给增广 图 2：建模三步与「占着的人能不能挪」的增广路。

把这套思路写成代码并验证：匈牙利算法对 200 组随机二分图与暴力枚举全量对照。用 Node.js 22.15.0 直接运行（node matching.js）：

'use strict';

// 匈牙利算法（增广路版本）：求二分图最大匹配
// 左侧 guest 0..n-1，右侧 room 0..m-1，edges[i] 为游客 i 可接受的房间列表
function maxMatching(n, m, edges) {
  const matchR = new Array(m).fill(-1); // 房间当前住着谁
  function tryKuhn(g, seen) {
    for (const r of edges[g]) {
      if (seen[r]) continue;
      seen[r] = true;
      // 房间空着，或者能让住客挪窝（增广路翻转），则匹配成功
      if (matchR[r] === -1 || tryKuhn(matchR[r], seen)) {
        matchR[r] = g;
        return true;
      }
    }
    return false;
  }
  let count = 0;
  for (let g = 0; g < n; g++) {
    if (tryKuhn(g, new Array(m).fill(false))) count++;
  }
  return { count, matchR };
}

// 暴力枚举做正确性对照（小规模）：枚举每个游客住哪间或不住
function bruteForce(n, m, edges) {
  let best = 0;
  const used = new Array(m).fill(false);
  function dfs(g, count) {
    if (g === n) { best = Math.max(best, count); return; }
    dfs(g + 1, count); // 游客 g 不住
    for (const r of edges[g]) {
      if (used[r]) continue;
      used[r] = true;
      dfs(g + 1, count + 1);
      used[r] = false;
    }
  }
  dfs(0, 0);
  return best;
}

// 概念图里的换房链场景：甲占着 A，乙只认 A，但甲也能去 B
const edges = [[0, 1], [0], [0, 1, 2]]; // 甲:{A,B} 乙:{A} 丙:{A,B,C}
let step = maxMatching(3, 3, edges.map((e) => [...e]));
console.log('换房链演示：甲:{A,B} 乙:{A} 丙:{A,B,C}');
console.log(`  甲先住 A；乙来时 A 被占，沿「乙→A→甲→B」增广：甲挪去 B，乙住进 A`);
console.log(`  最大匹配数：${step.count}，房间分配（房→客）：${step.matchR.join(', ')}`);

// 随机图 200 组与暴力对照
function mulberry32(seed) {
  return function () {
    seed |= 0; seed = (seed + 0x6D2B79F5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const rand = mulberry32(20261028);
let ok = 0;
for (let trial = 0; trial < 200; trial++) {
  const n = 1 + Math.floor(rand() * 6);
  const m = 1 + Math.floor(rand() * 6);
  const es = Array.from({ length: n }, () => {
    const list = [];
    for (let r = 0; r < m; r++) if (rand() < 0.5) list.push(r);
    return list;
  });
  if (maxMatching(n, m, es).count === bruteForce(n, m, es)) ok++;
}
console.log(`随机对照：200 组随机二分图，匈牙利与暴力枚举结果一致 ${ok}/200`);

实测输出：

换房链演示：甲:{A,B} 乙:{A} 丙:{A,B,C}
  甲先住 A；乙来时 A 被占，沿「乙→A→甲→B」增广：甲挪去 B，乙住进 A
  最大匹配数：3，房间分配（房→客）：1, 0, 2
随机对照：200 组随机二分图，匈牙利与暴力枚举结果一致 200/200

递归里那句 tryKuhn(matchR[r], seen) 就是「问占着的人能不能挪」的代码形态；seen 数组保证同一次增广里不重复探房，防止换人链绕成环。200 组随机对照全过，说明这个实现的不变量——每次成功都沿合法增广路翻转——立得住。

**常见误区。**一是贪心按顺序给游客分第一间满意的房，不再回头——不换人就会卡住，换房链演示里乙只认 A，不让甲挪就永远住不下三人；二是递归增广时不打 seen 标记，在环上无限递归；三是把带权最大满意度直接套无权匈牙利，带权版（KM 算法）要在相等子图上找增广路，是另一套实现；四是忘了先确认图真是二分——如果「房间之间」也有约束，模型就建错了。

AI 工程里任务调度、标注员分配、算力资源匹配都是它的变体，「先建模成图」永远是第一步。回到答题节奏：先讲建模三要素（左右集合、可选边、目标函数），再讲增广路直觉与换人链例子，最后按无权/带权区分匈牙利与 KM。你遇到过能把业务问题建成二分图的时刻吗？欢迎分享。