买域名之后怎样做网站,怎么做服装外贸网站,企业营销策划经营范围,儿童教育网站模板对于一般的二分图匹配我们肯定会想到匈牙利算法#xff0c;但是如果图中出现奇环怎么办#xff1f;此时匈牙利算法就不可以了#xff0c;就需要另一个算法#xff1a;带花树算法 主要就是为了解决奇环的问题 我们匹配时会发现#xff0c;如果存在奇环#xff0c;传统的匈…对于一般的二分图匹配我们肯定会想到匈牙利算法但是如果图中出现奇环怎么办此时匈牙利算法就不可以了就需要另一个算法带花树算法 主要就是为了解决奇环的问题 我们匹配时会发现如果存在奇环传统的匈牙利算法在一个奇环里至少有一个点不能匹配那么干脆就把这个奇环缩成一个点也叫开花这就是算法名字的由来在处理到奇环的时候把它缩成一个点路径取反的时候再暴力展开一个个取反。 缩点用并查集来维护
流程
参考代码 我们给所有点黑白染色。假设开始增广的点是黑点。把所有黑点压进队列中顺次处理。对于一个黑点u找与他相邻的点v会出现一下四种情况
1、u,v已经被缩成一个点了这两个点在一朵花里跳过。
2、v是白点说明已经被匹配了也就是偶环跳过。
3、v还没有被染色。那就先把这个点染成白的然后尝试与u匹配。如果v还没有匹配就匹配上增广成功然后沿增广路取反。如果v已经被匹配了那么匹配他的点就是个黑点染色然后压进队列。
4、v也是黑点。这时候染色发生了冲突说明遇见了奇环。这时候就需要找到两个点在带花树中的lca然后把这整个环缩成一个点。直接开花。
缩点开花过程 、找x和y的LCA的根L。找LCA可以用各种方法。。。直接朴素也行。 、在pre数组中把x和y接起来表示它们形成环了 3、从x、y分别走到L维护并查集使得变成一棵树同时沿路把pre数组连接起来。
题目
UOJ79 一般图最大匹配 从前一个和谐的班级所有人都是搞OI的。有 n 个是男生有 0 个是女生。男生编号分别为 1,…,n。 现在老师想把他们分成若干个两人小组写动态仙人掌一个人负责搬砖另一个人负责吐槽。每个人至多属于一个小组。 有若干个这样的条件第 v 个男生和第 u 个男生愿意组成小组。 请问这个班级里最多产生多少个小组
题解
就是带花树的模板题
代码
#include bits/stdc.h
#define ll long long
using namespace std;
const int N 510;
const int M 3e510;
struct node{ int to,nxt; }g[M];
int head[N],cnt;
int vis[N],match[N],f[N],pre[N],Id,id[N];
//vis[i]: 0(未染色) 1(黑色) 2(白色)
//match[i]: i的匹配点
//f[i]: i在带花树中的祖先
//pre[i]: i的非匹配边的另一点
//id: 找LCA用
int n,m,ans,u,v;
queueint q;
void Init()
{Idanscnt0;for(int i1;in;i)head[i]-1,id[i]match[i]0;
}
void add(int u,int v){ g[cnt]node{v,head[u]},head[u]cnt; }
int getf(int x){ return f[x]x?x:f[x]getf(f[x]); }
//查询x和y在带花树中的LCA
int LCA(int x,int y)
{//沿着增广路向上找lca for(Id;;swap(x,y))//x,y交替向上 if(x){xgetf(x);//有可能环中有环(花中有花)所以用并查集找祖先只处理祖先节点 if(id[x]Id) return x; //x,y在同一环中一定会找到已被编号的点该点即为LCA。 else id[x]Id,xpre[match[x]];//给点编号并沿着非匹配边向上找 }
}
//缩点开花
void blossom(int x,int y,int l)//将x、y到LCA(l)路径中的点缩为一点int l)
{ while(getf(x)!l){//增广路取反 pre[x]y;ymatch[x];//如果x、y的奇环中有白点将其染为黑点放入队列让其去找不是环中的匹配点 if(vis[y]2) vis[y]1,q.push(y);//只改变是根的点 if(getf(x)x) f[x]l;if(getf(y)y) f[y]l;//增广路取反 xpre[y];}
}
bool aug(int s)
{//每次都以s为起点bfs建带花树 for(int i1;in;i)vis[i]pre[i]0,f[i]i; while(!q.empty()) q.pop();q.push(s),vis[s]1;while(!q.empty()){uq.front();q.pop();for(int ihead[u];~i;ig[i].nxt){vg[i].to;//如果已经在同一个环(花)中或者是白点(意为这已经有匹配点)只接跳过 //这种情况不会增加匹配数 if(getf(u)getf(v)||vis[v]2) continue;//如果没有被染色 if(!vis[v]){//先染为白色将前继点指向u vis[v]2;pre[v]u;//如果没有被匹配过直接匹配成功 if(!match[v]){//增广路取反 for(int xv,last;x;xlast)lastmatch[pre[x]],match[x]pre[x],match[pre[x]]x; return 1;}//如果被匹配过则把匹配v的点染为黑色放入队列中 vis[match[v]]1;q.push(match[v]);}//v是黑色形成奇环则缩点(开花)。 else {int lcaLCA(u,v);blossom(u,v,lca);blossom(v,u,lca);}} }return 0;
}
int main(void)
{while(~scanf(%d%d,n,m)) {Init();while(m--){scanf(%d%d,u,v);add(u,v),add(v,u); } for(int i1;in;i)if(!match[i]aug(i))ans; printf(%d\n,ans);for(int i1;in;i)printf(%d%c,match[i], \n[in]);}return 0;
}
