C++信奥教学PPT：CSP_Ｓ_算法之二分图的染色、匈牙利算法（暑假精英班开招）

净化器（Purifying Machine, ACM/ICPC Beijing 2005, UVa1663）给m个长度为n的模板串。每个模板串包含字符0、1和最多一个星号“*”，其中星号可以匹配0或1。倒如，模板01*可以匹配010和011两个串，而模板集合{*01, 100,011}可以匹配串{001, 101, 100, 011}。你的任务是改写这个模板集合，使得模板的个数最少。例如，上述模板集合{*01, 100,011}可以改写成{0*1, 10*}，匹配到的字符串集合仍然是{001, 101, 100, 011}。n≤10，m≤1000。

【分析】拿到一个输入串之后，首先展开成可以匹配的串集合S，S中的元素用对应的整数值来表示。例如{*01, 100, 011}{101, 001, 100, 011}{5, 1, 4, 3}。两两判断这个S中的点s1, s2，如果二者的二进制只有一位不同，在s1和s2之间连一条边，对应一个带“*”的模板串，其中“*”的位置就是s1和s2不同的那一位。而s1和s2中1的个数的奇偶性必然不同。可以按照这个奇偶性将所有点分成两类，就形成一个二分图。而这个二分图的每一个匹配都对应于一个带“*”的模板集合。求此二分图的最大匹配，假设其中有n条边，则所求的模板集合的最小值就是|S|-n。

机器人警卫（Sentry Robots, ACM/ICPC SWERC 2012, UVa12549）在一个Y行X列（1≤Y, X≤100）的网格里有空地（.）、重要位置（*）和障碍物（#），如图2.74所示。用最少的机器人看守所有重要位置。每个机器人要放在一个格子里，面朝上、下、左、右4个方向之一。机器人会发出激光，一直射到障碍物为止，沿途都是看守范围。机器人不会阻挡射线，但不同的机器人不能放在同一个格子。

把每一行看作一个X结点，每一列看作一个Y结点，每个重要位置看作一条边连接相应的行结点和列结点。同一行或列只需要放置一个机器人，就可以看守所在同一行或同一列上的所有重要位置。这样就要求选择一组结点，使得每个所有重要位置对应的边都至少有1个结点被覆盖。这样就转换成为求二分图的最小覆盖，可以证明最小覆盖等于最大匹配数。