2020-2021:teams:hotpot:带花树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:带花树 [2020/05/22 17:22] lotk |
2020-2021:teams:hotpot:带花树 [2020/05/22 17:34] (当前版本) lotk |
||
|---|---|---|---|
| 行 151: | 行 151: | ||
| =====例题===== | =====例题===== | ||
| - | 由于这个算法使用较少，用到也基本上是模板，这里给出一道模板题。 | + | 由于这个算法使用较少，用到也基本上是模板，这里给出一道模板题。[[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/带花树.1590139320.txt.gz · 最后更改: 2020/05/22 17:22 由 lotk
