题链：uoj#79. 一般图最大匹配 题意： 从前一个和谐的班级，所有人都是搞OI的。有 n个是男生，有0个是女生。 有若干个这样的条件：第v个男生和第 u个男生愿意组成小组。 请问这个班级里最多产生多少个小组？
题解： 一般图最大匹配 带花树算法
真·存模板系列
#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<iostream> #include<algorithm> using namespace std; #define maxn 201000 #define N 600 struct node { int x,y,next; }a[maxn*2];int len,first[N]; void ins(int x,int y) { len++;a[len].x=x;a[len].y=y; a[len].next=first[x];first[x]=len; } int fa[N],n; int ffind(int x) {return (x!=fa[x])? fa[x]=ffind(fa[x]):fa[x];} int tim,vis[N]; int match[N],mark[N],next[N]; //mark是点类型的标记S=1,T=2,还有free //match存它的匹配点 //next数组是用来标记花朵中的路径的，综合match数组来用，实际上形成了双向链表，如(x, y)是匹配的，next[x]和next[y]就可以指两个方向了。 //怎么说 我觉得这个next是记录路径的 就是不是花上的点也要记录找到它的路径 int merge(int x,int y) { int fx=ffind(x),fy=ffind(y); if (fx!=fy) fa[fx]=fy; } queue<int> q; int LCA(int x,int y) { tim++; while (1) { if (x!=-1) { x=ffind(x); if (vis[x]==tim) return x; vis[x]=tim; if (match[x]!=-1) x=next[match[x]]; else x=-1; } int tt=x;x=y;y=tt; } } //缩花 void shrink(int x,int rt) { while (x!=rt) { int y=match[x],z=next[y]; if (ffind(z)!=rt) next[z]=y; //把花上的点都设为S并加到队列里进行增广 //因为奇环中的点都有机会向环外找到匹配 if (mark[y]==2) {q.push(y);mark[y]=1;} if (mark[z]==2) {q.push(z);mark[z]=1;} merge(x,y);merge(y,z); x=z; } } void augment(int now) { tim=0; for (int i=1;i<=n;i++) next[i]=-1,vis[i]=0,mark[i]=0,fa[i]=i; while (!q.empty()) q.pop(); q.push(now);mark[now]=1; while (!q.empty())//加进来的点都是S型点 { int x=q.front();q.pop(); if (match[now]!=-1) return; for (int k=first[x];k!=-1;k=a[k].next) { int y=a[k].y; if (match[x]==y || ffind(x)==ffind(y)) continue; //是匹配点或者在同一朵花里也不管 //我觉得在同一朵花里是不能管吧说明y也在队列里也能去增广 if (mark[y]==2) continue;//如果y是T型点就不管了 if (mark[y]==1) //y是S型点的话(x也是S型点) 就说明找到奇环了要缩花 { //缩点 int rt=LCA(x,y); if (ffind(x)!=rt) next[x]=y; if (ffind(y)!=rt) next[y]=x; shrink(x,rt);shrink(y,rt); }else if (match[y]==-1) //如果y是未配点就说明增广成功了 { //翻转交替路 next[y]=x; for (int u=y;u!=-1;) { int v=next[u]; int nt=match[v]; match[u]=v;match[v]=u; u=nt; } break; //如果不是奇环上的点的增广 那么翻转交替路之后now也找到了匹配 //而是的话，因为奇环中的点只能有一个匹配一次 所以有一个找到了之后也要退出了 }else { next[y]=x; q.push(match[y]); mark[match[y]]=1; mark[y]=2; } } } } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int m,i,x,y,ans; scanf("%d%d",&n,&m); len=0;memset(first,-1,sizeof(first)); for (i=1;i<=m;i++) { scanf("%d%d",&x,&y); ins(x,y);ins(y,x); } ans=tim=0; memset(match,-1,sizeof(match)); for (i=1;i<=n;i++) if (match[i]==-1) augment(i);//给i找匹配 for (i=1;i<=n;i++) if (match[i]!=-1) ans++; ans/=2; printf("%d\n",ans); for (i=1;i<=n;i++) if (match[i]!=-1) printf("%d ",match[i]); else printf("0 "); return 0; }转载于:https://www.cnblogs.com/Euryale-Rose/p/6527793.html
