HDU 1083

二分圖的最大匹配。。直接用套用匈牙利算法即可。

下面是AC代碼：
[cpp] 
#include<cstdio> 
#include<cstring> 
using namespace std; 
const int maxn = 110; 
bool g[3*maxn][3*maxn]; 
int match[3*maxn]; 
bool vis[3*maxn]; 
int p,n; 
bool dfs(int cur){ 
     for(int i=1;i<=n;i++){ 
          if(g[cur][i]==true&&!vis[i]){ 
                vis[i]=true; 
                int t=match[i]; 
                if(t==-1||dfs(t)){ 
                   match[i]=cur; 
                   return true; 
                } 
          } 
     } 
     return false; 
} 
int hungary(){ 
    int res=0; 
    for(int i=1;i<=n;i++)  match[i]=-1; 
 
    for(int i=1;i<=p;i++){ 
        memset(vis,false,sizeof(vis)); 
        if(dfs(i))  res++; 
    } 
    return res; 
} 
int main(){ 
    int t,num,a; 
    scanf("%d",&t); 
    while(t--){ 
        scanf("%d%d",&p,&n); 
        memset(g,false,sizeof(g)); 
        for(int i=1;i<=p;i++){ 
            scanf("%d",&num); 
            for(int j=1;j<=num;j++){ 
                scanf("%d",&a); 
                g[i][a]=true; 
            } 
        } 
        if(p==hungary()){ 
           printf("YES\n"); 
        } 
        else{ 
           printf("NO\n"); 
        } 
    } 
    return 0; 
}