2020-2021:teams:hotpot:带花树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:带花树 [2020/05/22 17:18] lotk |
2020-2021:teams:hotpot:带花树 [2020/05/22 17:34] (当前版本) lotk |
||
|---|---|---|---|
| 行 129: | 行 129: | ||
| 4.$father:$ 这个点所属的花，若不属于任何花则置为本身。为了方便输出方案，我们不进行显式缩点。因此需要引入这个指针。 | 4.$father:$ 这个点所属的花，若不属于任何花则置为本身。为了方便输出方案，我们不进行显式缩点。因此需要引入这个指针。 | ||
| + | {{:2020-2021:teams:hotpot:带花树14.png?400|}} | ||
| + | ====增广过程==== | ||
| + | |||
| + | 我们一次从每一个孤立点开始宽搜，并依次用i和o标记图上的点: | ||
| + | |||
| + | 1.若寻找到一个未被标记的未匹配点：将其标记为i型点，找到一条增广路，更新并维护该增广路的信息，完成增广。 | ||
| + | |||
| + | 2.若寻找到一个未被标记的点，但其已经被匹配，将其标记为i型点，并将其匹配的点标记为o型点，加入队列。 | ||
| + | |||
| + | 3.若寻找到一个已经被标记的i型点，说明此时构成偶环，直接无视。 | ||
| + | |||
| + | 4.若寻找到一个已经被标记的o型点，说明此时构成奇环且构成花，在当前扩展出的交错路上找到其公共祖先lca,lca此时为花根，沿着两侧的花边爬到花根，将路径上的结点father指针更新，标记全部更新为o，并将pre指针变为双向指针。 | ||
| + | |||
| + | ====指针定义==== | ||
| + | |||
| + | 为什么链的交错路上的pre是单向指针，而花上的pre指针式双向指针？ | ||
| + | |||
| + | 因为在链的交错路上增广方向确定，只需要单向指针即可，而花上我们不确定会从什么方向增广，故需要双向指针。 | ||
| + | |||
| + | =====例题===== | ||
| + | |||
| + | 由于这个算法使用较少，用到也基本上是模板，这里给出一道模板题。[[http://uoj.ac/problem/79|UOJ#79 一般图最大匹配]] | ||
| + | |||
| + | ====代码实现==== | ||
| + | |||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include<algorithm> | ||
| + | #include<stack> | ||
| + | #include<ctime> | ||
| + | #include<cstring> | ||
| + | #include<cmath> | ||
| + | #include<iostream> | ||
| + | #include<iomanip> | ||
| + | #include<cstdio> | ||
| + | #include<queue> | ||
| + | #include<vector> | ||
| + | using namespace std; | ||
| + | inline int read(){ | ||
| + | int num=0,f=1;char x=getchar(); | ||
| + | while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();} | ||
| + | while(x>='0'&&x<='9'){num=num*10+x-'0';x=getchar();} | ||
| + | return num*f; | ||
| + | } | ||
| + | const int maxn=505; | ||
| + | int n,m,ti; | ||
| + | vector<int> l[maxn]; | ||
| + | int match[maxn],fa[maxn],pre[maxn]; | ||
| + | int ty[maxn],vst[maxn]; | ||
| + | int getf(int x){ | ||
| + | return (x==fa[x])?x:fa[x]=getf(fa[x]); | ||
| + | } | ||
| + | int LCA(int x,int y){//找到花根 | ||
| + | ++ti; | ||
| + | x=getf(x);y=getf(y); | ||
| + | while(vst[x]!=ti){ | ||
| + | if(x){ | ||
| + | vst[x]=ti; | ||
| + | x=getf(pre[match[x]]); | ||
| + | } | ||
| + | swap(x,y); | ||
| + | } | ||
| + | return x; | ||
| + | } | ||
| + | queue<int> Q; | ||
| + | void blossom(int x,int y,int lca){//从两个冲突点开始，将所有的i型点加入可增广的队列中，即开花操作。 | ||
| + | while(getf(x)!=lca){ | ||
| + | pre[x]=y; | ||
| + | y=match[x]; | ||
| + | if(ty[y]==1){ | ||
| + | ty[y]=0; | ||
| + | Q.push(y); | ||
| + | } | ||
| + | if(getf(x)==x)fa[x]=lca; | ||
| + | if(getf(y)==y)fa[y]=lca; | ||
| + | x=pre[y]; | ||
| + | } | ||
| + | } | ||
| + | int aug(int s){ | ||
| + | for(int i=1;i<=n;++i)fa[i]=i,ty[i]=-1; | ||
| + | while(!Q.empty())Q.pop(); | ||
| + | ty[s]=0;Q.push(s); | ||
| + | while(!Q.empty()){ | ||
| + | int nw=Q.front();Q.pop(); | ||
| + | for(int nxt:l[nw]){ | ||
| + | if(ty[nxt]==-1){ | ||
| + | pre[nxt]=nw; | ||
| + | ty[nxt]=1; | ||
| + | if(!match[nxt]){//找到增广路直接增广 | ||
| + | for(int to=nxt,from=nw;to;from=pre[to]){ | ||
| + | match[to]=from; | ||
| + | swap(match[from],to); | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | ty[match[nxt]]=0; | ||
| + | Q.push(match[nxt]); | ||
| + | }else if(ty[nxt]==0&&getf(nw)!=getf(nxt)){//发现冲突且这朵花上的信息还未更新 | ||
| + | int lca=LCA(nw,nxt); | ||
| + | blossom(nw,nxt,lca); | ||
| + | blossom(nxt,nw,lca); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | return false; | ||
| + | } | ||
| + | int main(){ | ||
| + | n=read();m=read(); | ||
| + | for(int i=1,x,y;i<=m;++i){ | ||
| + | x=read();y=read(); | ||
| + | l[x].push_back(y); | ||
| + | l[y].push_back(x); | ||
| + | } | ||
| + | int ans=0; | ||
| + | for(int i=1;i<=n;++i) | ||
| + | if(!match[i])ans+=aug(i); | ||
| + | printf("%d\n",ans); | ||
| + | for(int i=1;i<=n;++i)printf("%d ",match[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
2020-2021/teams/hotpot/带花树.1590139124.txt.gz · 最后更改: 2020/05/22 17:18 由 lotk
