板子题,学了个带花树算法。
时间复杂度O(n^3)用于求一般图的最大匹配,即有奇环的图。
struct edge{ int to,next; }E[max_m<<1]; int head[max_n]; int cnt=1; void add(int from,int to){ E[cnt].to=to; E[cnt].next=head[from]; head[from]=cnt++; } int par[max_n],pre[max_n],link[max_n],ans; deque<int> q; char ty[max_n]; int findp(int x){return x==par[x]?x:par[x]=findp(par[x]);} int Ti=0,times[max_n]={}; int lca(int x,int y){ for(Ti++;times[x]!=Ti;x^=y^=x^=y) if(x) times[x]=Ti,x=findp(pre[link[x]]); return x; } void blossom(int x,int y,int p){ while(findp(x)!=p){ pre[x]=y; y=link[x]; par[x]=par[y]=p; if(ty[y]==1) ty[y]=2,q.push_back(y); x=pre[y]; } } bool Match(int x,int n){ for(int i=0;i<=n;i++) ty[i]=0,par[i]=i; q.clear(); ty[x]=2,q.push_back(x); while(q.size()){ x=q.front(),q.pop_front(); for(int i=head[x];i;i=E[i].next){ int u = E[i].to; if(ty[u]==0){ ty[u]=1; pre[u]=x; if(link[u]) q.push_back(link[u]),ty[link[u]]=2; else { for(;x;u=x){ x=link[pre[u]]; link[u]=pre[u]; link[link[u]]=u; } return 1; } } else if(ty[u]==2&&findp(u)!=findp(x)){ int p=lca(x,u); blossom(x,u,p),blossom(u,x,p); } } } return 0; } int Solve(int n){ int ans=0; for(int i=1;i<=n;i++) if(!link[i]&&Match(i,n)) ans++; return ans; }