网站上传图片加水印,桂林北站时刻表,国外做网站的软件,推广方式单一的原因正题
题目链接:https://www.luogu.com.cn/problem/P6113 题目大意
给出一张无向图#xff0c;求最大匹配。 1≤n≤103,1≤m≤51041\leq n\leq 10^3,1\leq m\leq 5\times 10^41≤n≤103,1≤m≤5104 解题思路
带花树的模板#xff0c;我也不会讲/kel
所以看下面两篇大佬的博…正题
题目链接:https://www.luogu.com.cn/problem/P6113 题目大意
给出一张无向图求最大匹配。
1≤n≤103,1≤m≤5×1041\leq n\leq 10^3,1\leq m\leq 5\times 10^41≤n≤103,1≤m≤5×104 解题思路
带花树的模板我也不会讲/kel
所以看下面两篇大佬的博客吧 yyb-带花树算法学习笔记 Bill Yang-带花树学习笔记
时间复杂度好像是O(n3)O(n^3)O(n3)的 code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N1010,M3e510;
struct node{int to,next;
}a[M];
int n,m,tot,tk,ans,ls[N],dfn[N];
int fa[N],pre[N],tag[N],match[N];
queueint q;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
int find(int x)
{return (fa[x]x)?x:(fa[x]find(fa[x]));}
int LCA(int x,int y){tk;xfind(x);yfind(y);while(dfn[x]!tk){dfn[x]tk;xfind(pre[match[x]]);if(y)swap(x,y);}return x;
}
void Blossom(int x,int y,int lca){while(find(x)!lca){pre[x]y;ymatch[x];if(tag[y]2){tag[y]1;q.push(y);}fa[x]fa[y]lca;xpre[y];}return;
}
int Aug(int s){memset(tag,0,sizeof(tag));memset(pre,0,sizeof(pre));for(int i1;in;i)fa[i]i;while(!q.empty())q.pop();q.push(s);tag[s]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(!tag[y]){tag[y]2;pre[y]x;if(!match[y]){for(int uy,lst;u;ulst)lstmatch[pre[u]],match[u]pre[u],match[pre[u]]u;return 1;}tag[match[y]]1;q.push(match[y]);}else if(tag[y]1find(y)!find(x)){int lcaLCA(x,y);Blossom(x,y,lca);Blossom(y,x,lca);}}}return 0;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}for(int i1;in;i)if(!match[i])ansAug(i);printf(%d\n,ans);for(int i1;in;i)printf(%d ,match[i]);return 0;
}
