这一题是一个很裸的二分图。每次以当前的问题编号连接两个锦囊的编号，跑一遍二分图就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #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)
