这一题是一个很裸的二分图。每次以当前的问题编号连接两个锦囊的编号，跑一遍二分图就可以了。
#include<cstdio>
#include<cstring>
int link[1005],n,m,h[1005],en,b[1005],ans;
struct Edge{
int b,next;
}e[1005];
void Add(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
int Find(int u){
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(b[v])continue;
b[v]=1;
if(!link[v] || Find(link[v])){
link[v]=u;
return 1;
}
}
return 0;
}
int main(){
freopen("1191.in","r",stdin);
freopen("1191.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int sa,sb;
scanf("%d %d",&sa,&sb);
Add(i,sb+1);
Add(i,sa+1);
}
for(int i=1;i<=m;i++){
memset(b,0,sizeof(b));
if(Find(i))ans++;
else break;
}
printf("%d\n",ans);
return 0;
}
评论 (0)
