先来讲一个需要用到的定理（太懒不想打）

 

     KONIG定理的证明

转自我左边的xyy大佬

• 定理内容：二分图最小点覆盖数等于最大匹配数。

• 证明：

假设现在已经找出了二分图最大匹配，匹配数为 n，为了证明定理，需要证明

一、n个点可以覆盖所有边

对于当前已经取出最大匹配的二分图，只存在以下三种边：１匹配边，２一个点盖一个点未盖的非匹配边（左盖右未盖和左未盖右盖），３左盖右盖。 

从未盖点搜索增广路（虽然已经不存在了，但用同样的方法搜），搜到的路径结尾一定是同侧的盖点，因为如果找到了异侧的未盖点就产生了增广路，与条件不符。对于这样的一条路（”W”形），如果有k个匹配，就可以用k个点覆盖。于是第２种边已经被完全覆盖了。 

再看剩下的，没有被未盖点搜到的，由１和３组成的交错路（”N”形，第一条和最后一条边均为１匹配边），如果有k个匹配，也可以用k个点覆盖。 

由此，３种边已经全部被覆盖，并且因为被未盖点搜到的匹配边和搜不到的匹配边没有交集，且并集即所有匹配边（仿佛是废话），所以我们只用了每个匹配边的一个节点，所以n个点可以覆盖所有边得证。

二、少于n个点不能覆盖所有边

考虑从已选的点中去掉一个。 

如果这个点在”W”形路上，无论如何也无法覆盖所有边。 

如果在”N”形路上也一样。（仿佛也是废话）

于是就愉快地得出了扣你吉定理。实际上他的得出还是依赖于匈牙利算法找增广路的思路。

---

 

 

以下是一个模板题

A - 最大匹配

 题意：一共有N个学生跟P门课程,一个学生可以任意选一门或多门课,问是否可行。

1.每个学生选的都是不同的课(即不能有两个学生选同一门课)

  2.每门课都有一个代表(即P门课都被成功选过)

题解：就是匈牙利算法啦（题目输入和处理有点毒），还有最后输出大写YES。。。。

1 var 2 map:array[0..600,0..600]of longint; 3 mx,my:array[0..2000] of longint; 4 vis:array[0..2000] of boolean; 5 p,m,t,i,l,ans,x,j,y:longint; 6  7 function dfs(s:longint):boolean; 8  var i:longint; 9  begin10    for i:=1 to m do11     begin12       if (map[s,i]=1)and(not vis[i])  then13         begin14          vis[i]:=true;15           if (my[i]=0)or(dfs(my[i])) then//当前这个点未被访问或者是一条增广路16              begin17               mx[s]:=i;// 左边点s对应右边点i18               my[i]:=s;19               exit(true);//可行返回true20             end;21        end;22     end;23     exit(false);24  end;25 begin26  readln(t);27 for l:=1 to t do28 begin29    fillchar(map,sizeof(map),0);30    fillchar(mx,sizeof(mx),0);31   fillchar(my,sizeof(my),0);32  readln(p,m);33  for i:=1 to p do34   begin35     read(x);36     for j:=1 to x do37      begin38        read(y);39        map[i,y]:=1;40      end;41      readln;42   end;43 44   ans:=0;45   for i:=1 to p do//用课程匹配学生46    begin47      fillchar(vis,sizeof(vis),false);48      if dfs(i) then inc(ans);49    end;50 51    if ans=p then  writeln('YES') else writeln('NO');52 end;53 end.