最大匹配数就等于最大点覆盖，因为在图里面，凡是要覆盖的点必定是连通的，而最大匹配之后，若还有点没有覆盖到，则必定有新的匹配，与最大匹配数矛盾，如果去掉一些匹配，则必定有点没有覆盖到。
POJ 1469
比较简单，用的经典的二分图匹配算法。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int p[500][510],c[500][510];
int vis[510];
int lefts[510];
int cp[500],cc[500],n,m;
void init()
{
memset(vis,0,sizeof vis);
memset(lefts,-1,sizeof lefts);
memset(cp,0,sizeof cp);
memset(cc,0,sizeof cc);
memset(p,0,sizeof p);
memset(c,0,sizeof c);
}
bool match(int u)
{
for (int j=0;j<cp[u];j++){
int v=p[u][j];
if (1){
vis[v]=1;
if (lefts[v]==-1 || match(lefts[v])){
lefts[v]=u;
return true;
}
}
}
return false;
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
init();
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
int tmp,t2;
scanf("%d",&tmp);
for (int j=0;j<tmp;j++){
scanf("%d",&t2);
p[t2][cp[t2]++]=i;
c[i][cc[i]++]=t2;
}
}
int ans=0;
for (int i=1;i<=m;i++){
memset(vis,0,sizeof vis);
if (match(i)) ans++;
}
//cout<<ans<<endl;
if (ans==n) puts("YES");
else puts("NO");
}
return 0;
}
POJ 3041
最小覆盖问题，转化为求最大匹配
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int mat[510][510],cnt[510]; int vis[510],lefts[510]; int n,k; bool match(int u) { for (int i=0;i<cnt[u];i++){ int v=mat[u][i]; if (!vis[v]){ vis[v]=1; if (lefts[v]==-1 || match(lefts[v])){ lefts[v]=u; return true; } } } return false; } int main() { while (scanf("%d%d",&n,&k)!=EOF) { memset(mat,0,sizeof mat); memset(cnt,0,sizeof cnt); int a,b; for (int i=0;i<k;i++){ scanf("%d%d",&a,&b); mat[a][cnt[a]++]=b; } memset(lefts,-1,sizeof lefts); int ans=0; for (int i=1;i<=n;i++){ memset(vis,0,sizeof vis); if (match(i)) ans++; } printf("%d ",ans); } return 0; }