- 玄关求调
qiutiao
- @ 2025-8-26 14:47:51
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 条评论
-
-
#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