刚了解很不熟练，有问题请及时指出 QAQ
带花树
带花树通常用于解决一般图最大匹配问题。
至于一般图最大权匹配问题，毒瘤请移步这里。
考虑如何处理奇环，让环上的点两两匹配，总会剩下一个点，而且每一个环上的点都存在一种环上匹配方案使得该点被剩下，那么考虑将环缩成点，缩完的点一样可以匹配。
如果要支持输出方案，那么是不能实质缩点的，用并查集即可。
定义匹配的一对点分别为黑点和白点。
算法流程：
- 从一个没有匹配出发，初始定义该点的颜色为黑。
for(int i=1;i<=n;++i) if(!match[i]&&solve(i)) ++ans; - 每一次从队列里取出节点 $u$ 进行更新：
- 如果相邻点 $v$ 在当前轮还没有被染色
-
如果 $v$ 被匹配了
那么将匹配拆散，$v$ 当前为白点，将其匹配的点染成黑点，并扔进队列继续匹配，如果 $v$ 的匹配点找到了合适的匹配，那么 $v$ 可以和当前的起点 $i$ 匹配，将多增加一组匹配。
q.push(match[v]),col[match[v]]=1; - 如果 $v$ 没有匹配
将 $v$ 匹配给起点 $i$ ，至于怎么维护可以每一个点记录 $pre$ ，然后暴力跳链更新：
for(int las;u;v=las,u=pre[v]) las=match[u],match[u]=v,match[v]=u; return true; - 如果相邻点 $v$ 的颜色是白
那么不用管，因为遇见了一个偶环。
- 如果相邻点 $v$ 的颜色是黑
-
如果 $v$ 和 $u$ 已经是同一个花里的了
那么不用管。
-
否则
暴力开花，先找到 $lca$ ，显然花将包括 $u$ 到 $v$ 路径上的所有点 (花)。
找到 $lca$ 后，分别从 $u$ 和 $v$ 开始往上面跳，并更新 $pre$ ，由于是花，花内的 $pre$ 一定是双向的，跳的时候还需要检查颜色，如果跳到的点 $x$ 是白色，那么染色为黑扔进队列，因为将花看做点的话是可以往外面匹配的，由于我们不确定是花中的哪个节点往外匹配，故均染色为黑。
注意跳的时候还需要更新并查集的 $fa$ 。
带花树的时间复杂度是 $O(n^3)$ 的，但在实际实现中跑不到上界，因此一般 $n=1000$ 也能跑跑。
关于跳 $lca$ 和开花两个部分没看懂 (代码) 的建议画画图：
蓝点即为黑点，橙点即为白点，粗边即为匹配，有向的细边其实就是 $pre$ 指针。
一些题目
模板题。
$\rm{Code_1:}$
namespace _ {
queue <int> q;
int tim,fa[N],vis[N],pre[N],col[N],match[N];
inline int find(int x) {
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
}
inline int lca(int x,int y) {
++tim,x=find(x),y=find(y);
for(;;swap(x,y)) {
if(!x) continue;
if(vis[x]==tim) return x;
vis[x]=tim,x=match[x]?find(pre[match[x]]):0;
}
}
inline void blossom(int x,int y,int t) {
while(find(x)!=t) {
pre[x]=y,y=match[x];
if(col[y]==2) col[y]=1,q.push(y);
fa[x]=fa[y]=t,x=pre[y];
}
}
inline bool solve(int s) {
memset(pre,0,sizeof(pre));
memset(col,0,sizeof(col));
for(int i=1;i<=n;++i) fa[i]=i;
while(!q.empty()) q.pop();
q.push(s),col[s]=1;
while(!q.empty()) {
int u=q.front();q.pop();
for(int v:G[u]) {
if(!col[v]) {
col[v]=2,pre[v]=u;
if(!match[v]) {
for(int las;u;v=las,u=pre[v])
las=match[u],match[u]=v,match[v]=u;
return true;
} else q.push(match[v]),col[match[v]]=1;
} else if(col[v]==1&&find(u)!=find(v)) {
int t=lca(u,v);
blossom(u,v,t),blossom(v,u,t);
}
}
}
return false;
}
} using namespace _;
int main() {
IN(n),IN(m);
for(int i=1;i<=m;++i) addedge();
for(int i=1;i<=n;++i) if(!match[i]&&solve(i)) ++ans;
printf("%d\n",ans);
return puts(""),0;xuyaozhuyi
}
可以将一个筐子拆成三个点，对于一个球也要和这三个点连边，并且三个点之间连边。
如果一个筐子是合法的，那么筐子的三个点之间一定存在一个匹配。
由于每一个球一定匹配，答案为最大匹配数 $-n$ 。
注意点数是 $n+m+m+m$ 而非 $n$ ，清空数组或者定义 $fa$ 时需要注意。
$\rm{Code_2:}$
namespace Flower_tree {
queue <int> q;
int tim,fa[N],vis[N],pre[N],col[N],match[N];
inline int find(int x) {
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
}
inline int lca(int x,int y) {
++tim,x=find(x),y=find(y);
for(;;swap(x,y)) {
if(!x) continue;
if(vis[x]==tim) return x;
vis[x]=tim,x=match[x]?find(pre[match[x]]):0;
}
}
inline void blossom(int x,int y,int t) {
while(find(x)!=t) {
pre[x]=y,y=match[x];
if(col[y]==2) col[y]=1,q.push(y);
fa[x]=fa[y]=t,x=pre[y];
}
}
inline bool check(int s) {
memset(pre,0,sizeof(pre));
memset(col,0,sizeof(col));
for(int i=1;i<=L;++i) fa[i]=i;
while(!q.empty()) q.pop();
q.push(s),col[s]=1;
while(!q.empty()) {
int u=q.front();q.pop();
for(int v:G[u]) {
if(!col[v]) {
col[v]=2,pre[v]=u;
if(!match[v]) {
for(int las;u;v=las,u=pre[v])
las=match[u],match[u]=v,match[v]=u;
return true;
} else q.push(match[v]),col[match[v]]=1;
} else if(col[v]==1&&find(u)!=find(v)) {
int t=lca(u,v);
blossom(u,v,t),blossom(v,u,t);
}
}
}
return false;
}
inline int solve() {
int ans=0;
for(int i=1;i<=L;++i) if(!match[i]&&check(i)) ++ans;
return ans;
}
} using namespace Flower_tree;
inline void Main() {
memset(match,0,sizeof(match)),
memset(vis,0,sizeof(vis)),tim=0;
IN(n),IN(m),IN(e),L=n+m+m+m;
for(int i=1;i<=L;++i) G[i].clear();
int x,y;
for(int i=1;i<=e;++i) {
IN(x),IN(y);
addedge(x,n+y),addedge(x,n+m+y),addedge(x,n+2*m+y);
}
for(int i=1;i<=m;++i)
addedge(n+i,n+m+i),addedge(n+i,n+2*m+i),addedge(n+m+i,n+2*m+i);
printf("%d\n",solve()-n);
for(int i=1;i<=n;++i) printf("%d ",(match[i]-n-1)%m+1);
return puts(""),void();
}
int T;
int main() {
IN(T);
while(T--) Main();
return 0;
}
1 条评论
ticmis · 2020年5月14日 10:20 上午
orz%%