「学习笔记」二分图

点击查看目录

目录

• 「学习笔记」二分图
  • 知识点
    • 定义及判定
    • 二分图最大匹配
    • 二分图最小点覆盖
    • 二分图最大独立集
  • 例题
    • P7368 [USACO05NOV]Asteroids G
      • 思路
    • P2319 [HNOI2006]超级英雄
      • 思路
    • Way Selection
      • 题意
      • 思路
    • 文理分班
      • 题意
      • 思路
    • 放置机器人
      • 题意
      • 思路
    • 猫和狗
      • 题意
      • 思路

知识点

定义及判定

定义：存在一种方案把点分为两个集合，使得同一个集合内的点没有连边的图。

比如这张图（by OI-Wiki）：

判定：没有奇环。

考虑染色法，左边集合的点染成 \(1\)，左边集合的点染成 \(0\)。如果存在奇环则会有一个点不知道染成什么颜色，因此不是二分图。如果不存在奇环，所有点都会正常染色，分为两个点集，因此是二分图。

二分图最大匹配

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

有一个方法是转换成网络流用 Dinic 算法解决，Link等写完网络流学习笔记再挂链接。

本文主要讲解增广路算法（\(\text{Augmenting Path Algorithm}\)）。

几个定义：

• 匹配边/非匹配边：当前选上/没选上的番。
• 交错路：匹配边与非匹配边相间的一条路。
• 增广路：以非匹配边开头和结束的一条交错路。

算法过程用一个例子说明：

这是初始图：

\(1\) 匹配了一个点 \(4\)：

\(2\) 尝试匹配 \(4\)，但失败了。

于是从 \(2\) 出发走一个增广路。

将路上的匹配边变为非匹配边，非匹配边变为匹配边，这样匹配数就会加一。

\(3\) 尝试匹配 \(6\)，但失败了。

于是从 \(3\) 出发走一个增广路。

将路上的匹配边变为非匹配边，非匹配边变为匹配边，匹配数就会加一。

然后就匹配完成了，最大匹配值为 \(3\)。

代码：

ll n,  jl[N], p[N], ans;
std::vector <ll> tu[N];
bool AugmentationPath (ll u) {
	far (v, tu[u]) {
		if (jl[v]) continue;
		jl[v] = 1;
		if (!p[v] || AugmentationPath (p[v])){
			p[v] = u;
			return true;
		}
	}
	return false;
}
inline void Solve () {
	_for (i, 1, n) {
		memset (jl, 0, sizeof (jl));
		ans += AugmentationPath (i);
	}
	return;
}

二分图最小点覆盖

最小点覆盖：选最少的点，满足每条边至少有一个端点被选。

König 定理：二分图中，最小点覆盖 = 最大匹配。

证明

参考文章

例图：

（图是搬过来的，我也不知道为什么他从右边开始跑）

首先对一个二分图跑完最大匹配，然后考虑构造一个点集：

从右边未匹配点出发，尽力走交错路，在经过的点上打标记。这条交错路一定是由一条非匹配边开头，匹配边结尾的交错路，否则就不是最大匹配了。

选左边的标记点和右边的未标记点构成一个点集，这个点集就是一个最小点覆盖，其大小等于最大匹配。

为什么这个点集就是最小点覆盖？思考以下三个问题。

这个点集为什么是一个点覆盖？

不难发现当一条边左边点没被标记，右端点被标记的时候才不会被选。

• 当这条边是一条匹配边时，因为走交错路上的匹配边的时候就是从左边走到右边的，所以左边点一定会先被标记，然后走到右边才会标记右端点。
• 当这条边不是一条匹配边时，因为走交错路上的非匹配边的时候就是从右边走到左边的，所以右端点被标记后，一定会走到左边并标记左端点。

因此这种边是不存在的，所以不会存在任何一条边不被选，因此这是一个点覆盖。

---

其大小为什么等于最大匹配？

对这个点覆盖内的每个点进行分析：

• 如果这个点是左边的标记点，它一定是在交错路上因为有一条向右的匹配边而被走到从而标记的。
• 如果这个点是右边的无标记点，它一定因为有一条向左的匹配边才不会被当做起点走交错路而被标记。

每个点都覆盖到了一条匹配边，两个点不会覆盖同一条匹配边，一条匹配边必定会被覆盖。因此这个点覆盖内的点与最大匹配内的点一一对应，数量相等。

---

这个点集为什么就是一个最小点覆盖？

设最大匹配数为 \(k\)。

两个点不会覆盖同一条匹配边，一条匹配边必定会被覆盖。

因此，一个点覆盖的数量不可能少于 \(k\) 个点。

我们已经构造出了大小为 \(k\) 的点覆盖，因为大小不可能再少了，所以这个点集为什么就是一个最小点覆盖！

---

解决这三个问题后，就可以得出结论了：最小点覆盖 = 最大匹配！

---

二分图最大独立集

最大独立集：选最多的点，满足两两之间没有边相连。

定义也可以变为：选最多的点，满足每条边至多有一个端点被选。

那不就是最小点覆盖的补集吗？

所以大小是最大匹配 - 最小点覆盖。

例题

二分图的题目基本都是将题意抽象成一个二分图，然后直接跑板子，难点在于建模，所以我不放次要的代码了。

P7368 [USACO05NOV]Asteroids G

思路

建模为二分图：把列当成左边点集，行当成右边点集，第 \(i\) 行第 \(j\) 列的点当做第 \(i\) 行和第 \(j\) 列所代表的点的连边。

要求选的列数和行数最小，覆盖所有点，建模为二分图后其实就等价于最小点覆盖了。

P2319 [HNOI2006]超级英雄

思路

建模为二分图：把题当成左边点集，「锦囊妙计」当成右边点集，在每道题和其能够使用的两种「锦囊妙计」连边。

然后跑一个最大匹配，注意当前必须匹配上才能进入下一题，所以匹配失败时直接退出。

Way Selection

题意

小杉家族 \(r\) 个人正在一片空地上散步，突然，外星人来了…… 留给小杉家族脱逃的时间只有 \(t\) 秒，每个小杉都有一个跑的速度 \(v\)。总共有 \(a\) 个传送点，小杉们必须在 \(t\) 秒内到达传送点才能脱逃。另外一个小杉进入一个传送点以后，该传送点就会消失 现在请你安排一种方案，使脱逃的小杉尽可能的多。

\(0<a,r,t\le1000\)。

思路

建模为二分图：把人当成左边点集，传送点当成右边点集，当 \(\operatorname{dis}(人,传送点)\le vt\) 时在两者之间连边。

文理分班

题意

jzyz 每年的文理分班的时候，每个班都会有一些同学分到其他班，还会进入一些其他班的同学进入这个班。

小 x 负责安排座位，为了照顾分班带来的那种伤感情绪，小 x 制定了很人性化的座位安排计划，具体计划如下：

比如 A 和 B 都是本班学生且是好朋友，A 分到了其他班，而 C 则是外班进入这个班的，C 和 A 并不熟悉，而 C 和 B 关系很好，那么小 x 为了照顾 A 和 C 的情绪，就会让 B 坐在 A 的位置，C 坐在 B 的位置。

当然，实际情况可能很复杂，比如一个班里的同学之间关系不一定好，外班进来的可能和本班很多人关系都很好。

现在告诉你，和小 x 所在班有关系的人一共有 \(n\) 个人，小 x 想知道有没有一个合理的方案来满足自己的座位安排计划。

对于 \(100\%\) 的数据满足 \(1\le n\le50,1\le T\le 20\)。

思路

首先把题意翻译成人话：自己认识自己，如果 A 认识 B，A 就可以坐到 B 的位置上。

建模为二分图：把原来班的同学（的座位）当成左边点集，现在班里的同学当成右边点集，当两者认识时在两者之间连边。

当最大匹配数等于现在班里的同学数时，存在合法方案。

放置机器人

题意

Robert 是一位著名的工程师。一天他的老板给了他一个任务。任务的背景如下：

给出一张由方块组成的地图。方块有许多种：墙，草，和空地。老板想让 Robert 在地图上放置尽可能多的机器人。每个机器人拿着一把激光枪，它可以同时向东西南北四个方向射击。机器人必须一直呆在它开始时被放在的位置并且不断地射击。激光束当然可以经过空地或草地，但不能穿过墙。机器人只能被放在空地上。当然老板不希望看到机器人相互攻击。换句话说，两个机器人不能被放在一条线上（竖直或水平），除非它们中间有一堵墙。

由于你是一位机智的程序员和 Robert 的好基友之一，他请你帮他解决这个问题。也就是说，给出地图的描述，计算地图上最多能放置的机器人数量。

\(1\le m,n\le50\)。

思路

与 Asteroids G 比较像，但是由于有「墙」挡着，左右点集内的点不应是整个列和行，而是能尽量延长的横线/竖线。

猫和狗

题意

小 k 同学正在玩一个游戏，在游戏中他扮演了一个马戏团的老板，现在小 k 同学需要利用马戏团中的A只猫和B只狗举办一次表演，表演之前他让观众进行了投票，投票的类容是：我想看到第___号猫/狗的表演，不想看到第___号猫/狗的表演。注意到每个观众都是更喜欢猫或更喜欢狗，所以两个空后面一定会被勾上不同的内容。喜欢猫的观众会在第一空后面选择猫，第二空后面选择狗；反之就会在第一空后面选择狗，第二空后面选择猫。对于每一个观众，只有当 TA 投票的内容都被满足了（即 TA 想看到的动物出场表演，TA 不想看到的动物不参与表演）的时候，TA 才会来看表演。当然啦，看表演是要付门票钱的，作为马戏团的老板，小 k 自然是希望来的人越多越好了。他想找到一个安排动物表演的方案，使得来看表演的观众尽量多。

对于 \(100\%\) 的数据，\(n,m\le300,k\le500\)。

思路

建模为二分图：把喜欢猫的人当成左点集，喜欢狗的人当成右点集，当 A 喜欢的猫/狗和 B 不喜欢的猫/狗相同时在两者之间连边。

不难发现跑个最大独立集即可。