UOJ-79 一般图的最大匹配(带花树模板求解)
#79. 一般图最大匹配
从前一个和谐的班级，所有人都是搞OI的。有 n 个是男生，有 0 个是女生。男生编号分别为 1,…,n 。
现在老师想把他们分成若干个两人小组写动态仙人掌，一个人负责搬砖另一个人负责吐槽。每个人至多属于一个小组。
有若干个这样的条件：第 v 个男生和第 u 个男生愿意组成小组。
请问这个班级里最多产生多少个小组？
输入格式
第一行两个正整数， n,m 。保证 n≥2 。
接下来 m 行，每行两个整数 v,u 表示第 v 个男生和第 u 个男生愿意组成小组。保证 1≤v,u≤n ，保证 v≠u ，保证同一个条件不会出现两次。
输出格式
第一行一个整数，表示最多产生多少个小组。
接下来一行 n 个整数，描述一组最优方案。第 v 个整数表示 v 号男生所在小组的另一个男生的编号。如果 v 号男生没有小组请输出 0 。
模板代码：
#include <algorithm>
#include <string.h>
#include <cstdio>
using namespace std;
const int maxn = 505;
const int maxm = 124755*2;
struct node{int v, next;} edge[maxm];
int no, head[maxn];
int n, m;
int match[maxn];
int pre[maxn]; //记录增广路中非匹配边
int mk[maxn], f[maxn]; //mk记录当前点是哪种类型： -1(未访问过)，0(S型)，1(T型)
int front, tail, q[maxn]; //模拟队列
int TIM, vis[maxn]; //对于lca的标记及时间轴
void init()
{
no = 0;
memset(head, -1, sizeof head);
}
inline void add(int u, int v)
{
edge[no].v = v, edge[no].next = head[u];
head[u] = no++;
}
int getf(int x) {return x == f[x]? x: f[x]=getf(f[x]);}
int lca(int u, int v) //巧妙地求法
{
++TIM;
while(vis[u] != TIM)
{
if(u != 0)
{
u = getf(u); //花根
if(vis[u] == TIM) return u;
vis[u] = TIM;
if(match[u] != -1) u = getf(pre[match[u]]);
//每一个S点的配偶(也就是T点)的pre 都是指向它的父亲的,于是就直接这么跳就可以
else u = 0;
//必须要到花根再进行操作，因为只有花根的pre才只想该花真正的父亲
}
swap(u, v);
}
return u;
}
void change(int u, int v, int _lca) //缩花，将花上的所有点通过并查集缩为一点
{
while(getf(u) != _lca)
{
pre[u] = v;
int t = match[u];
mk[t] = 0;
q[tail++] = t;
if(tail >= maxn) tail = 1;
if(getf(t) == t) f[t] = _lca;
if(getf(u) == u) f[u] = _lca;
v = t;
u = pre[v];
}
}
bool bfs(int X) //寻找增广路
{
for(int i = 1; i <= n; ++i)
f[i] = i, mk[i] = -1;
front = tail = 1;
q[tail++] = X, mk[X] = 0;
while(front < tail)
{
int u = q[front];
for(int k = head[u]; k+1; k = edge[k].next)
{
int v = edge[k].v;
if(match[v] == -1 && v != X)
//当且仅当v没被匹配且不为X
{
pre[v] = u;
int t, las, now = v;
//将增广路上的匹配边->未匹配边，未匹配边->匹配边
while(now != -1)
{
t = pre[now];
las = match[t];
match[t] = now, match[now] = t;
now = las;
}
return true;
}
if(mk[v] == -1) //找到未访问的点，继续扩展
{
mk[v] = 1;
pre[v] = u;
mk[match[v]] = 0;
q[tail++] = match[v];
if(tail >= maxn) tail = 1;
}
else if(mk[v] == 0 && getf(u) != getf(v)) //遇到奇环，且之前未缩花
{
int _lca = lca(u, v);
change(u, v, _lca);
change(v, u, _lca);
}
}
++front;
if(front >= maxn) front = 1; //模拟循环链表
}
return false;
}
void work()
{
memset(match, -1, sizeof match);
int ans = 0; TIM = 0;
for(int i = 1; i <= n; ++i)
if(match[i] == -1 && bfs(i))
++ans;
printf("%d\n", ans);
for(int i = 1; i <= n; ++i)
printf("%d%c", match[i]==-1? 0: match[i], i==n? '\n': ' ');
}
int main()
{
while(~scanf("%d %d", &n, &m))
{
init();
for(int i = 1; i <= m; ++i)
{
int u, v;
scanf("%d %d", &u, &v);
add(u, v); add(v, u);
}
work();
}
return 0;
}
学自博文：
http://blog.csdn.net/qq_36797743/article/details/60968291
http://fanhq666.blog.163.com/blog/static/8194342620120304463580/