最小点覆盖概念：选取最小的点数覆盖二分图中的所有边。
最小点覆盖 = 最大匹配数。
证明：首先假设我们求的最大匹配数为m，那么最小点覆盖必然 >= m,因为仅仅是这m条边就至少需要m个点。然后假如我们已经求得最小覆盖点集，那么在点集中每个点必然有着这样的性质，在于它相连的边里面，一定有一条边的端点不在最小点集中，因为如果连一条这样的边都没有，那这个点完全没有在最小点集的必要，我们任意选取这样的一条边，一定可以形成一个匹配，匹配数与最小点集中的点的个数相等，但现在这仅仅是一个匹配，他必然小于最大匹配，所以最小点覆盖 <= m，综上所述，最小点覆盖 = 最大匹配数，证明成立。
ps：这个证明是我从网上看明白后总结出来的，个人感觉学姐的证明过于笼统，所以就放在了这里，感觉这个更加严密易懂（学知识要学明白嘛～）。
代码如下：实现方法：基础匈牙利算法。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 1510 int n; struct EDGE { int to,nxt; } edge[10*maxn]; int head[maxn],vis[maxn],match[maxn],tot; void add_edge(int u,int v) { edge[tot].to = v; edge[tot].nxt = head[u]; head[u] = tot++; } bool Find(int u) { for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].to; if(!vis[v]) { vis[v] = 1; if(match[v] == -1 || Find(match[v])) { match[v] = u; return true; } } } return false; } int slove() { memset(match,-1,sizeof(match)); int ans = 0; for(int i = 0; i < n; i++) { memset(vis,0,sizeof(vis)); if(Find(i)) ans++; } return ans; } int main() { int num,a,b,t; while(~scanf("%d",&t)) { n = t; memset(head,-1,sizeof(head)); tot = 0; while(t--) { scanf("%d:(%d)",&a,&num); for(int i = 0;i < num;i++) { scanf("%d",&b); add_edge(a,b); add_edge(b,a); } } int ans = slove()/2; printf("%d\n",ans); } return 0; }