不少人可能为找不到非传统题型的练习题而头疼。这几天我专门发出一些用于省选集训的题目供大家参考。

Problem 1: cell 手机
题目来源：USACO Contest FEB06 Gold (Translated by Matrix67)

问题描述
    奶牛们已经开始使用手机交流了，但它们发现手机的按键设计不适合它们的蹄子。它们想设计一个新的手机，让它的按键更少，但是更大。
    它们喜欢普通手机的一个功能：词语联想。每个按键都有一些字母和它对应，打出一个单词只需要按对应的按键。因为一个按键可能对应多个字母，因此某些单词可能会发生“歧意”。不过，大多数时候这种歧意可以通过用字典判断的方法来消除。
    考虑到奶牛们在自定义一款新的手机，它们还需要用奶牛字母表替换英文字母表。神奇的是，奶牛字母表中的字母恰好是英语字母表中的前L个字母，即使顺序也一样。它们想知道如何把这些字母分配给B个按键(1<=B<=L)使得在字典中不会产生歧意的单词最多。就像普通的手机一样，他们希望每个按钮上的字母都是字母表中一段连续的字母。

    这是一个答案提交类的题目。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件cell.3.in相对应的输出文件应该为cell.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入数据
    第一行：一个整数N，表示这是第N个输入文件。
    第二行：两个用空格隔开的整数：B和L
    第三行：D，字典中的单词数(1<=D<=1000)
    第四行到第D+3行：每一行包含一个字典中的单词，用1到10个大写字母表示。这些单词按照字典序给出，并且保证没有重复。

输出数据
    第一行：字典中具有唯一的按钮序列的单词数。
    第二行到第B+1行：其中的第n行包含有第n个按钮上的字母，用大写的字母按照字典的顺序表示。所有行必须按照字典序排列，每个字母出现恰好一次。如果有多个最优解，选用第一个按键上字母最多的解。如果最优解仍然不唯一，考虑第二个按键上字母最多，依此类推。

样例输入(cell.1.in)
1
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK

样例输出(cell.1.out)
7
AB
CDEFGHIJK
LM

样例说明
    第一个按键上只有AB两个字母，第二个按键上含有C到K，第三个按键上为LM。单词CELL、DILL、FILL和FILM的输入都是2233，其它7个单词的输入都是唯一的。

题解(Ctrl+A)：
    这道题目……搜索，乱搞。

Problem 2: selfstr 自描述序列
题目来源：Matrix67根据经典问题改编

问题描述
    “这句话里有1个数字零，2个数字一，1个数字二，0个数字三”。

    在N(N>=2)进制中只允许0到N-1这N个数字出现。一个N位的N进制数（允许有前导0）可以由另一个同样多位的数来描述。我们定义一个N位N进制数的描述序列为：左起第i个数字为原数中数字i-1出现的次数。
    例如，在4进制中，0023的描述序列为2011，因为0023中有2个0，0个1，1个2和1个3。
    我们惊奇地发现，4进制数1210的描述序列是它本身！我们称这样的数叫做“自描述序列”。

    你需要编写程序计算出在某个进制下的自描述序列。一个进制下的自描述序列可能有很多个，你只需要给出其中一个即可。
    这是一个答案提交类的问题。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件selfstr.3.in相对应的输出文件应该为selfstr.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入格式
    输入数据只有一个正整数N

输出格式
    输出N个字符，它表示N进制下的自描述序列。在高于10的进位制下，大于9的数字请用大写字母表示。
    如果有多种可能的解，你只需要输出其中一个。
    如果该进制下无解，请输出“NONE”。

样例输入(selfstr.1.in)
4

样例输出(selfstr.1.out)
1210

题解：
    这道题太有意思了！首先，你需要先算几个小数据。你会发现，算到N>=6后，渐渐有规律了：

   N   N进制下的自描述序列
   4    1210 or 2020
   5    21200
   6    NONE
   7    3211000
   8    42101000
   9    521001000

    事实上，这道题目就是考你当搜索到一些解后能不能找到规律得到所有解。这里我们发现，对所有N>6，至少存在一个解为R21(0…0)1000，其中R=N-4，中间0的个数为N-7。结论显然正确。
    有可能除了这个之外存在其它的解，因此我们仍然需要写一个check来核对答案。

Problem 3: relation 大小关系
题目来源：Matrix67根据经典问题改编

问题描述
    用关系“ < ”和“ = ”将3个数a、b、c依次序排列时，有13种不同的序列关系：
      a=b=c, a=b<c, a<b=c, a<b<c, a<c<b
      a=c<b, b<a=c, b<a<c, b<c<a, b=c<a
      c<a=b, c<a<b, c<b<a

    用这两种关系连接N个数有多少种不同的方案？

    这是一个答案提交类的问题。所有选手将得到10个输入数据，你只需要在你自己的计算机上计算出你的答案，然后把你的答案提交上来。与输入文件relation.x.in相对应的输出文件应该为relation.x.out，这里x表示一个1到10之间的数。

输入格式
    输入一个整数，表示N。

输出格式
    输出用小于和等于符号将N个数进行有序排列的方案数。

样例输入(relation.1.in)
3

样例输出(relation.1.out)
13

题解：
    组合数学+高精度。由于数据规模很小，我就直接搞成了答案提交类的题目。
    下面给出两种递推方法：
    Solution 1: N个数中必然存在一个最大的“等价类”，如果这个等价类里有k个数，那么剩下的数就有F(N-k)种排列方案。别忘了我们需要枚举这k个数是哪k个数。于是，F(N)
=C(N,1)F(N-1)+C(N,2)F(N-2)+C(N,3)F(N-3)+ … +C(N,N)F(0)
    Solution 2: 用F[ i, j]表示 i个数中有j 个等价类的排列方案（就是说有j-1个小于符号）。第 i个数有可能并入了F[i-1, j]中的 j个等价类中的一个，也有可能不与任何一个已有的数相等，独自成为一个等价类插入F[i-1, j-1]里产生的 j个空位中。于是，F[ i,j ]=F[i-1, j]*j + F[i-1,j-1]*j。

其它问题：
    如何用Cena评测答案提交类问题？
        见http://www.matrix67.com/blog/article.asp?id=176
    这些题的数据哪里有？
        第一题：http://ace.delos.com/FEB06，GOLD DIVISION里面的第三个
        第二题：自己写check，不需要数据
        第三题：http://www.research.att.com/~njas/sequences/b000670.txt，吓死你

Matrix67原创
转贴请注明出处

    说到概率，有些好玩的东西不得不提。比如，你知道吗，23个人中至少两个人生日相同的概率竟然超过了1/2；假如你们班上有50个人的话，那更不得了，至少两人生日相同的概率达到97% ！如果你会计算这个概率问题的话，你可以亲自证实这一点。本文适宜的读者是知道上述问题怎么算的高中朋友，上述问题也是高中阶段学的一些基本概率知识。
    上面的问题都是简单概率，它包含了一个最基本的原则，即使没有系统地学习过，平常人们也都在无形之中使用它：概率等于你要算的东西除以总的数目。比如。我们要计算23个人中任何两个人都不在同一天生的概率。假设2月29日与其它日期出现概率相同的话（这是为了便于计算我们做出的假设，它有悖于常理），那么它的概率为A(366,23)/366^23。它约为0.493677。因此，至少两人在同一天生的概率为1-0.493677=0.506323。当然，对于“你要算的东西除以总的数目”的认识是片面的，比如“投两个骰子出现的数字和从2到12共有11种可能，问数字和大于10的概率”这一问题的答案并不是2/11，因为这11个点数和出现的概率不是相等的，我们只能从投出的两个数字共6*6=36种情况中进行统计，可能的情况只有(5,6)、(6,5)和(6,6) （不会有人说还有(6,7)之类的吧），答案应该是3/36=1/12。这些都是废话，我不细说了。
    但是，你有想过这个问题吗：要是这些数目是无穷的怎么办？换句话说，统计的东西不是“离散”的怎么办？比如看这样一个问题。明天早上我要和MM约会，但是具体见面时间我忘了，好像是8:00-9:00的某个时候。那么我随便在这个时段中选一个时间去等MM，最多等她半个小时，正好能见到MM的概率是多少（假设MM先到的话不会等我）。这个问题和我们平时见到的问题不同的地方在于，它的“情况”是连续的，不是离散的，不能逐一统计数目。咋办呢？我们注意到，我的时间随机取一个，MM的时间随机取一个，对于某些组合我们是有缘分的（这些组合无穷多）。这些组合正好对应了平面区域上的点。就是说，搞一个横坐标表示我的时间，纵坐标表示MM的时间，那么肯定能画出那么一块区域，区域里的所有点(x,y)对应所有我和MM可能相见的组合。任何一个时间组合有多大的可能落在这个区域呢？由于在矩形区域内点(x,y)是均匀分布的，我们只需要计算一个面积之比就行了。下图中显而易见，答案是3/8。
  

    一个类似的问题是Buffon投针实验。有一个人，叫Buffon。他在地板上画了很多间隔相同的平行线，然后叫了一帮狐朋狗友来，把一些长度相同的针扔在地上。然后，他统计有多少针和地板上的线相交，并宣称可以得到圆周率π的值。换句话说，一根针投到间隔相同的平行线中，与平行线相交的概率和π有关。我们时常感到数学的神奇之处，比如当这个π在很多不该出现的场合莫明其妙的出现时。例如，Stirling近似公式（黑书上的这个公式写错了）出现了π值：n!≈sqrt(2πn) * (n/e)^n （sqrt是开方的意思）。再比如，两个整数互质的概率是6/(π^2)，而无穷级数1+1/4+1/9+1/16+…=(π^2)/6。当然，还有最神奇的e^(πi)+1=0。现在，π又出现在了这样一个看似与圆周率更加没有关系的概率问题中：针与线相交的概率为两倍针的长度除以平行线的间隔再除以π。这个结论的证明和刚才我等MM的问题是一样的。建立这样一个坐标系，x轴是针的中点到离它最近的那根平行线的距离，y轴是针与平行线的夹角。我们一定能做出这样一块“可行区域”，这块可行区域中的点(x,y)所对应的针的位置和平行线相交。然而，这块区域的面积并不像刚才那么简单，它是由一些方程围出来的图形，求这块区域的面积需要使用定积分。这里就不再接着说了，反正能求出来。
    当然，涉及无穷的概率问题还有很多其它的统计方法，这里不说明了。

    有这么一个笑话。据说一个飞机上有炸弹的概率为十万分之一，但某人并不认为这个概率很小。概率小毕竟意味者可能，每天航班这么多，十万分之一确实不是一个小数目。因此，这个人从来不敢坐飞机。有一次，他居然和朋友上了飞机，朋友吃惊地问，你咋不害怕了。他说，飞机上有一个炸弹的概率不是十万分之一么？那么飞机上同时有两个炸弹的概率就是一百亿分之一了，对吧。朋友说，对，一百亿分之一已经很小了。这人说，那好，我自己已经带了一颗炸弹上来。
    从没听过这个笑话的人或许会笑笑说那人真傻，但仔细想想似乎自己解释一下也很困难。这涉及到了条件概率，这在高中课本里（至少在我的高中课本里）没有说过，你把书翻烂了都找不到。
    条件概率，顾名思义，就是有条件的概率。比如，有两个炸弹的概率和知道已经有一个炸弹后存在两个炸弹的概率是不同的。假如我们把有两个炸弹的概率记作P(两个炸弹)=百亿分之一，那么后一个问题就是P(两个炸弹|已经有一个炸弹了)。记号P(A|B)就表示在B已经发生了的情况下，A的概率是多少。后面我们可以知道，它仍然等于十万分之一。
    换一个问题。还记得最前面我们说的“投两个骰子出现的数字和大于10的概率”这个问题吗？它的答案是3/36。现在改一下，如果我们事先就知道至少有一个骰子是6点。那么概率变成多少了（或者问概率变了没有）？很显然，多了一个条件，概率肯定变大了，笨蛋都知道如果有一个骰子搞出那么大一个点数，那赢的几率肯定增加了。关键在于，前面分析过数字和大于10的情况只有(5,6)、(6,5)和(6,6)，它们本来就含有6啊，为什么概率变了。仔细思考发现，原来是总的情况变少了。原来总的情况是36种，但如果知道其中一个骰子是6点的话，情况数就只有11种了。概率变成了3/11，大了不少。我们还需要补充，如果把我们“至少有一个骰子是6点”换成“至少有一个骰子是5点”的话，总的情况数还是11，但3/11将变成2/11，因为有一种情况(6,6)不满足我的已知条件。我们可以纯粹用概率来描述这一个思考过程。如果P(E)表示点数和大于10的概率，P(F)表示至少有一个5点的概率，那么我们要求的是P(E|F)，即已知F发生了，求E发生的概率。于是P(E|F)=P(E∩F)/P(F)。这就是条件概率的公式。简单说明一下就是，E∩F表示满足E的情况和满足F的情况的交集，即同时满足E和F的所有情况。P(E∩F)就是E和F同时发生的概率。这个公式使用原来的非条件概率（总情况数目还是36时的概率）之比来表示条件概率（相当于分式同时除以一个数，就如P(E|F)=2/11=(2/36)/(11/36)）。回到炸弹问题上，P(A|B)就应该等于出现两个炸弹的概率除以出现一个炸弹，他仍然等于一个炸弹的概率。
    高中课本里对“独立事件”的定义是模糊的。其实，现在我们可以很好地给独立事件下定义。如果事件E和事件F独立，那么F就不能影响E，于是P(E|F)=P(E)。把P(E|F)展开，就成了P(E∩F)/P(F)=P(E)，也即P(E∩F)=P(E)*P(F)。这不就是“两个独立事件同时发生的概率”的计算公式么。

 
   条件概率的应用很广泛，下面举个例子。
    有两个人，他们每三句话只有一句是真的（说真话的概率是1/3）。其中一个人说，Matrix67是女的。另一个人说，对。那么，Matrix67的确属于女性的概率是多少？
    这是一个条件概率问题。如果P(E)表示Matrix67是女性的概率，P(F)表示第二个人说“对”的概率，那么我们要求的就是P(E|F)，即在第二个人回答后的情况下第一个人说的话属实的概率。按照公式，它等于P(E∩F)/P(F)。P(E∩F)是说，Matrix67是女的，第二个人也说对，表示的实际意义是两个人都说的真话，他的概率是1/3 * 1/3=1/9。P(F)表示第二个人说“对”的概率，这有两种情况，有可能他说对是因为真的是对的（也即他们俩都说真话），概率仍是1/9；还有一种可能是前一个人撒谎，第二个人也跟着撒谎。他们都说谎的可能性是2/3 * 2/3 =4/9。没有别的情况会使第二个人说“对”了，因此P(F)=1/9+4/9=5/9。按照条件概率的公式，P(E|F)=P(E∩F)/P(F)=(1/9) / (5/9)=1/5。后面我们接着说，这其实是Bayes定理的一个非常隐蔽的形式。

    你或许看过我的这篇日志：http://www.matrix67.com/blog/article.asp?id=87。我用相当长的篇幅介绍了Monty Hall问题。下面所要讲的东西与这个有关，建议你先去看看那篇日志。不看也没啥，我把题目意思在下面引用一下。

    这个问题最初发表在美国的一个杂志上。美国有一个比较著名的杂志叫Parade，它的官方网站是http://www.parade.com。这个杂志里面有一个名字叫做Ask Marylin的栏目，是那种“有问必答”之类的一个Q&A式栏目。96年的时候，一个叫Craig.F.Whitaker的人给这个栏目写了这么一个问题。这个问题被称为Monty Hall Dilemma问题。他这样写到：

    Suppose you're on a game show, and you're given the choice of three doors. Behind one door is a car, behind the others, goats. You pick a door, say number 1, and the host, who knows what's behind the doors, opens another door, say number 2, which has a goat. He says to you, "Do you want to pick door number 3?" Is it to your advantage to switch your choice of doors?

    这个问题翻译过来，就是说，在一个游戏中有三个门，只有一个门后面有车，另外两个门后面是羊。你想要车，但你不知道哪一个门后面有车。主持人让你随便选了一个门。比如说，你选择了1号门。但你还不知道你是否选到了车。然后主持人打开了另一扇门，比如2号。你清楚地看到2号门后面是一只羊。现在主持人给你一个改变主意的机会。请问你是否会换选成3号门？
    对于这个问题，Marylin的回答是：应该换，而且换了后得到车的概率是不换的2倍。

    对于这个问题，十年来涌现出了无数总也想不通的人，有一些冲在最前线的战士以宗教般的狂热传播他们的思想。为了说服这些人，人们发明创造了十几种说明答案的方法，画表格，韦恩图，决策树，假设法，捆绑法（我的那篇日志里也提到一种最常见的解释方法），但是都没用。这群人就是不相信换了拿到车的概率是2/3。他们始终坚定地认为，换与不换的概率同为1/2。下面，我们用一个更科学的方法来计算换了一个门后有车的概率。我们使用刚才学习的条件概率。

  
    上面的图表形象地表明了打开某个门的概率是几分之几。横坐标是选择的第几个门，纵坐标是门后面车与羊的排列。对于有些情况（非主对角线上的格子），主持人打开哪个门只有一种选择，我们把它标在这个格子上；对于对角线上的格子，打开门有两种选择，这两种选择出现的几率相等，因此我们用一条斜线划开。现在，还是假设我们选了1号门，那么此时我选到车的概率显然是1/3，同时，这个车在2号门后面的概率也是1/3，在3号门后面仍为1/3。当主持人打开了第2扇门后，我们需要计算一下这导致原来的这些1/3都变成了什么。我们要求在已经知道主持人亮出二号门后面的羊后车在这三个门后面的概率分别是多少。由于我“最初选择1号门”是整个问题的一个假设（大前提），因此对概率的计算只在我们图表中的第一列进行。我们用事件A、B、C分别表示车在1、2、3号门后的概率，事件D表示主持人打开了2号门。在第一列中，打开2号门的情况占了一格半，因此P(D)=1.5/3。A∩D和C∩D的部分分别用灰色和紫色画了出来，B∩D显然为空集。于是，P(A|D)=P(A∩D)/P(D)=(0.5/3) / (1.5/3)=1/3，结果1号门后面有车的概率仍然是1/3。显然，P(B|D)变成0了，因为P(B∩D)=0，B和D根本不可能同时发生。我们惊奇地发现，3号门后面有车的概率从1/3增加到了2/3，因为P(C|D)=P(C∩D)/P(D)=(1/3) / (1.5/3)=2/3。我们使用条件概率从理论上再一次得到了这个雷打不动的事实。

    我们最后看一个问题。这个问题是条件概率的终极应用，是概率学中一个最重要，应用最广的东西。把下面这个问题搞明白了，从此对概率学的学习就真正入门，可以摆脱“初级”、“菜鸟”的称号了。这就是传说中的Bayes定理。我已经写了五千字了，不想再写了，这保证是我想说的最后一个东西。
    首先你得知道，P(A|B)和P(B|A)是截然不同的两个概念。有些条件概率，正着算P(A|B)容易，把条件反过来算P(B|A)却无从下手，而人们往往更加关心P(B|A)。生活中有很多这样的例子，我们小举一个。
    某个地区性病传播飞快，性病患者高达15%。医院临床实验表明，对有性病的人检测，有95%的人显阳性；对没有性病的人检测，有2%的人阳性。现在，假如某个人搞了一个小MM，突然有点担心，跑到医院去检测，查出了阳性。那么他确实有性病的概率是多少？
    假如事件A是显阳性，B是有性病，我们可以看到在现实生活中P(A|B)比P(B|A)更容易得到。P(A|B)表示对有性病的人进行检测搞出阳性的概率，这可以通过医院里的抽样统计得到，题目中已经说了是95%。但是，P(B|A)就不好说了，它表示对于某个人来说，显阳性意味者真的有性病的概率是多少。这是针对个人的，统计资料通常没有这一项，但人们却往往更关心这个问题。事实上，我们可以通过已有的条件把P(B|A)算出来。把P(B|A)展开，它等于P(B∩A)/P(A)，而因为P(A|B)=P(A∩B)/P(B)，把P(B)乘过去，得到P(B∩A)=P(A∩B)=P(A|B)*P(B)。我们把分子的部分转换成了已知量P(A|B)和P(B)的乘积，它等于95% * 15%。那么P(A)怎么算呢？P(A)是由两种情况构成的，可能是有性病的人显的阳性，即P(A∩B)；也可能是没有性病的人显的阳性，即P(A∩～B)。～B表示B的补集，也可以在B上面画一条横线表示，我这里画不出来，算了。～B就是没有病的人，它的概率是1-15%=85%。P(A∩B)和P(A∩～B)都可以用已有的概率算出来，分别是刚才得到的P(A|B)*P(B)，以及用类似的方法得到的P(A|～B)*P(～B)。。因此整个概率就等于(95% * 15%)/(95% * 15% + 2% * 85%)≈0.8934。这就是Bayes定理的一个具体应用。
    在上面的题里，我们求P(A)时把“显阳性”按照“是否有病”分成了两个不相交的部分，并分别求
出概率后再求和。事实上，对于事件A可以按照B的属性分成多个不相交的部分。此时再完整地叙述一下Bayes定理，大家就不难理解了。如果B1、B2、B3一直到Bn是n个互不相交的事件，而且这n个事件是“一个完整的分类”（即并集是全集，包含了所有可能的情况），那么有公式：

P(B1|A)=[ P(A|B1)*P(B1) ]/[P(A|B1)*P(B1) + P(A|B2)*P(B2) + …+ P(A|Bn)*P(Bn)]

    下面再举一个例子。这个例子和前一个例子非常相似。事实上，它也和前面说我是女的的那个例子如出一辙。它将是我们的最后一个例子，并且我不给解答，写完例子立马走人。解决这个问题有助于理解和联系前面这两个例子。
    我经常约同学单独出去玩。据统计，和一个女同学出去玩的概率高达85%，和一个男同学出去的概率只有15%。现在，某人宣称他看到昨天我和某某男在外面玩。长期观察表明，这人的可信度（说真话的概率）为80%。那么，我昨天真和一个男的出去玩的概率是多少？

Matrix67原创
做人要厚道，转贴请注明出处

    如果你看不清楚第二个字母，下面有一个大号字体版本：

二分图最大匹配的König定理及其证明

    本文将是这一系列里最短的一篇，因为我只打算把König定理证了，其它的废话一概没有。
    以下五个问题我可能会在以后的文章里说，如果你现在很想知道的话，网上去找找答案：
    1. 什么是二分图；
    2. 什么是二分图的匹配；
    3. 什么是匈牙利算法；(http://www.matrix67.com/blog/article.asp?id=41)
    4. König定理证到了有什么用；
    5. 为什么o上面有两个点。

    König定理是一个二分图中很重要的定理，它的意思是，一个二分图中的最大匹配数等于这个图中的最小点覆盖数。如果你还不知道什么是最小点覆盖，我也在这里说一下：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。比如，下面这个图中的最大匹配和最小点覆盖已分别用蓝色和红色标注。它们都等于3。这个定理相信大多数人都知道，但是网络上给出的证明并不多见。有一些网上常见的“证明”明显是错误的。因此，我在这里写一下这个定理的证明，希望对大家有所帮助。

    假如我们已经通过匈牙利算法求出了最大匹配（假设它等于M），下面给出的方法可以告诉我们，选哪M个点可以覆盖所有的边。
    匈牙利算法需要我们从右边的某个没有匹配的点，走出一条使得“一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现”的路（交错轨，增广路）。但是，现在我们已经找到了最大匹配，已经不存在这样的路了。换句话说，我们能寻找到很多可能的增广路，但最后都以找不到“终点是还没有匹配过的点”而失败。我们给所有这样的点打上记号：从右边的所有没有匹配过的点出发，按照增广路的“交替出现”的要求可以走到的所有点（最后走出的路径是很多条不完整的增广路）。那么这些点组成了最小覆盖点集：右边所有没有打上记号的点，加上左边已经有记号的点。看图，右图中展示了两条这样的路径，标记了一共6个点（用 “√”表示）。那么，用红色圈起来的三个点就是我们的最小覆盖点集。
    首先，为什么这样得到的点集点的个数恰好有M个呢？答案很简单，因为每个点都是某个匹配边的其中一个端点。如果右边的哪个点是没有匹配过的，那么它早就当成起点被标记了；如果左边的哪个点是没有匹配过的，那就走不到它那里去（否则就找到了一条完整的增广路）。而一个匹配边又不可能左端点是标记了的，同时右端点是没标记的（不然的话右边的点就可以经过这条边到达了）。因此，最后我们圈起来的点与匹配边一一对应。
    其次，为什么这样得到的点集可以覆盖所有的边呢？答案同样简单。不可能存在某一条边，它的左端点是没有标记的，而右端点是有标记的。原因如下：如果这条边不属于我们的匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果这条边属于我们的匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的（想想匹配的定义），左端点就应该有标记。
    最后，为什么这是最小的点覆盖集呢？这当然是最小的，不可能有比M还小的点覆盖集了，因为要覆盖这M条匹配边至少就需要M个点（再次回到匹配的定义）。
    证完了。
  
Matrix67原创
做人要厚到 转贴请注明出处

    如图，蓝色三角形ABC，以AC和BC为边向外作黄色正方形，作CP垂直于AB且CP=AB并依P的位置作出两个平行四边形，平移图中红色、蓝色部分后，黄色部分面积相等，建立等量关系。