BZOJ 1191 [HNOI2006]超级英雄Hero 二分图最大匹配

题意: sb题 解析: 这篇题解的意义只是纪念我第一次封装的二分图=w= 代码:

namespace std;class Bipartite_Graph{#define N 1100private:int head[N],match[N],v[N];int cnt,n,m;int tim;struct Edge{int from,to,next;}edge[N<<1];void addedge(int from,int to){edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];head[from]=cnt++;}bool find(int x){for(int i=head[x];i!=-1;i=edge[i].next){int to=edge[i].to;if(v[to]!=tim){v[to]=tim;if(!match[to]||find(match[to])){match[to]=x;return 1;}}}return 0;}#undef Npublic:void build(){scanf(“%d%d”,&n,&m);memset(head,-1,sizeof(head));tim=0;for(int i=1;i<=m;i++){int x,y;scanf(“%d%d”,&x,&y);x++;y++;addedge(i,x),addedge(i,y);}}int Maximal_Matching(){int ret=0;for(int i=1;i<=m;i++){tim++;if(find(i))ret++;else break;}return ret;}}g;int main(){g.build();printf(“%d\n”,g.Maximal_Matching());}

，宁愿停歇在你门前的那棵树上，看着你，守护你。