这一题是一个很裸的二分图。每次以当前的问题编号连接两个锦囊的编号,跑一遍二分图就可以了。
#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; }