using namespace std;
int e[1001][1001];
int match[1001];
int book[1001];
int g,b;
int dfs(int u){
	int i;
	for(i=1;i<=b;i++){
		if(book[i+g]==0&&e[u][i+g]!=0){
			book[i+g]=1;//标记点i已经访问过 
			//如果点i未被配对或者找到了新的配对 
			if(match[i+g]==0||dfs(match[i+g])){
				//更新配对关系
				match[i+g]=u;
				match[u]=g+i;
				return 1; 
			} 
		}
	}
	return 0;
}

int main(){
	int i,j,t1,t2,sum=0,m=0;
	memset(e,1,sizeof(e));
	scanf("%d %d",&g,&b);
	for( i=1;i<=g;i++){
	    int tx;
	    cin>>tx;
	    for(j=1;j<=tx;j++){
	        scanf("%d",&t2);
	        e[i][g+t2]=0;
	        e[g+t2][i]=0;
	    }
	    if(i!=g){
	    e[i][i+1]=0;
	    e[i+1][i]=0;
		}
	}  
	for(int i=g;i<b+g;i++)e[i][i+1]=e[i+1][i]=0;
	{
	for(i=1;i<=g;i++)
		memset(book ,0, sizeof(book));
		if(dfs(i)){
			sum++;
		}
	}

    cout<<g+b-sum;
	return 0;
}

4 条评论

  • @ 2025-8-26 15:02:31

    60

    • @ 2025-8-26 15:02:13

      高额硬币啊

      • @ 2025-8-26 15:01:25

        76个币

        • @ 2025-8-26 14:58:51
          
          #include <bits/stdc++.h>
          using namespace std;
          int e[1001][1001];
          int match[1001];
          int book[1001];
          int g,b;
          int dfs(int u){
          	int i;
          	for(i=1;i<=b;i++){
          		if(book[i+g]==0&&e[u][i+g]!=0){
          			book[i+g]=1;//标记点i已经访问过 
          			//如果点i未被配对或者找到了新的配对 
          			if(match[i+g]==0||dfs(match[i+g])){
          				//更新配对关系
          				match[i+g]=u;
          				match[u]=g+i;
          				return 1; 
          			} 
          		}
          	}
          	return 0;
          }
          
          int main(){
          	int i,j,t1,t2,sum=0,m=0;
          	memset(e,1,sizeof(e));
          	scanf("%d %d",&g,&b);
          	for( i=1;i<=g;i++){
          	    int tx;
          	    cin>>tx;
          	    for(j=1;j<=tx;j++){
          	        scanf("%d",&t2);
          	        e[i][g+t2]=0;
          	        e[g+t2][i]=0;
          	    }
                  //
          	}  
          	for(i=1;i<=g;i++){//
          		memset(book ,0, sizeof(book));
          		if(dfs(i)){
          			sum++;
          		}
          	}
          
              cout<<g+b-sum;
          	return 0;
          }
          //12
          
          
          • 1