锐客网

  1. 首页 > it技术 > >

bzoj|带花树算法浅谈&&bzoj4405: [wc2016]挑战NPC

bzoj————图论带花树详解

带花树简介 带花树用来求解一般图的最大匹配问题。
前置技能 基础图论知识。
极大匹配：对于一个匹配，若无法在原图中找到任意边加入匹配，则称该匹配为一个极大匹配。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配 。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边 … 形成的路径叫交替路。
增广路：对于一条路径，从一个未匹配点出发，走交替路，终止于另一个未匹配点 ，则这条交替路称为增广路。显然增广路长度为奇数。1
带花树算法 考虑二分图最大匹配的Dinic做法实质上就是不断的找增广路，我们是否可以在一般图中同样用找增广路的方法来求解最大匹配？
考虑我们已经匹配好一些点，我们选择一个没有匹配的点进行bfs。从当前节点出发，将它标为S型。如果发现一个点没有被匹配，则我们就进行了一次成功的增广。否则我们建搜索树，将当前搜到的点标成T型，将它的配偶标成S型（即目前与它匹配的点），并把它的配偶加入队列。（与二分图匹配有点像）。搜索树以开始搜索的节点为根，深度为1。如图，虚线为有边但不是配偶，实线为两点为配偶。
bzoj|带花树算法浅谈&&bzoj4405: [wc2016]挑战NPC
文章图片

则发现2,3有配偶，就将他们标记为T，将他们的配偶标记为S，将他们的配偶加入队列。如图。红色为T，白色为S。
bzoj|带花树算法浅谈&&bzoj4405: [wc2016]挑战NPC
文章图片

但是我们匹配时会发现一些当前bfs已经标记过的点，如何处理？
显然我们现在一定在一个S点上。
（1）当我们找到1个T点时，如下图。
bzoj|带花树算法浅谈&&bzoj4405: [wc2016]挑战NPC
文章图片

我们相当于找到一个长度为偶数的环，我们可以无视这条边。
（2）当我们找到1个S点时，如下图。
bzoj|带花树算法浅谈&&bzoj4405: [wc2016]挑战NPC
文章图片

我们将这个环缩成一个点，将环内的点全变成S点，之后将缩完后的点加入队列。
bzoj|带花树算法浅谈&&bzoj4405: [wc2016]挑战NPC
文章图片

为什么可以缩点？
当这个环中任意一点找到了匹配点，则剩下的点都能够找到对应的匹配点。即缩点之前和缩点之后的图是否有增广路的情况是相同的。
写法 1.缩点。
2.修改ST。
3.维护一棵搜索树。
我们可以不显式表示花，记录pre数组表示当前增广的前驱。维护一个并查集。
1.当前找到的点是T型点：无视。
2.当前找到的点没有匹配：直接增广。
3.当前找到的点与现在的点在一个并查集：无视。
4.当前找到的点是S型点：缩点！
如何缩点？
找到x,y的lca（暴力即可），在pre数组中把它们连起来，然后从x,y走到lca，修改并查集和lca。
模板 下面是uoj#79 模板题。

#include #include #include #include #include using namespace std; queue q; int read() { char ch=getchar(); int f=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') {f=f*10+(ch^48); ch=getchar(); } return f; } int k,n,m; struct node { int from; int to; int next; }edge[500005]; int head[50005],ans=0,lca,l,pre[50005],ma[50005],fa[50005],st[50005],tot,d,v[50005]; void add(int u,int v) { edge[tot].from=u; edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int get_lca(int x,int y) { for(d++; ; swap(x,y)) if(x) { if(v[x]==d) return x; v[x]=d; x=fa[pre[ma[x]]]; } } void up(int x,int y) { while(fa[x]!=lca) { pre[x]=y; if(st[ma[x]]>0) { q.push(ma[x]); st[ma[x]]=0; } fa[x]=lca; fa[ma[x]]=lca; x=pre[y=ma[x]]; } } int match(int x) { for(int i=1; i<=n; i++) fa[i]=i,st[i]=-1; while(!q.empty()) q.pop(); q.push(x); st[x]=0; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x]; i!=-1; i=edge[i].next) { if(st[edge[i].to]<0) { st[edge[i].to]=1; pre[edge[i].to]=x; if(!ma[edge[i].to]) { int k,j; for(j=x,i=edge[i].to; j; j=pre[i=k]) { k=ma[j]; ma[j]=i; ma[i]=j; } return 1; } q.push(ma[edge[i].to]); st[ma[edge[i].to]]=0; } else if(fa[edge[i].to]!=fa[x]&&!st[edge[i].to]) { lca=get_lca(edge[i].to,x); up(edge[i].to,x); up(x,edge[i].to); for(int j=1; j<=n; j++) fa[j]=fa[fa[j]]; } } } return 0; } void solve() { for(int i=1; i<=n; i++) { ans+=!ma[i]&&match(i); } printf("%d\n",ans); for(int i=1; i<=n; i++) printf("%d ",ma[i]); } int main() { memset(head,-1,sizeof(head)); n=read(); m=read(); for(int i=1; i<=m; i++) { int x,y; x=read(),y=read(); add(x,y); add(y,x); } ans=0; solve(); }

bzoj4405: [wc2016]挑战NPC 【bzoj|带花树算法浅谈&&bzoj4405: [wc2016]挑战NPC】一眼是个二分图模型，然而却不能用二分图做，考虑建一般图，将一个筐拆成3个点，3个点互相连边，这样对于一个筐没有球时有1对匹配，1个球是有两对匹配，2个球时有两对匹配，3个球时有3对匹配，最后答案就是匹配数-n。
#include #include #include #include #include using namespace std; queue q; int read() { char ch=getchar(); int f=0; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0'; ch=getchar(); } return f; } int d,n,m,tot,head[10005],st[10005],ma[10005],v[10005],pre[10005],k,fa[10005],ans,lca; struct node { int from; int to; int next; }edge[1000005]; void add(int u,int v) { edge[tot].from=u; edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } void ins(int u,int v) { add(u,v); add(v,u); } int get_lca(int x,int y) { for(d++; ; swap(x,y)) if(x) { if(v[x]==d) return x; v[x]=d; x=fa[pre[ma[x]]]; } } void up(int x,int y) { while(fa[x]!=lca) { pre[x]=y; if(st[ma[x]]>0) { q.push(ma[x]); st[ma[x]]=0; } fa[x]=lca; fa[ma[x]]=lca; x=pre[y=ma[x]]; } } bool match(int x) { for(int i=1; i<=n+3*m; i++) fa[i]=i,st[i]=-1; while(!q.empty()) q.pop(); q.push(x); st[x]=0; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x]; i!=-1; i=edge[i].next) { if(st[edge[i].to]<0) { st[edge[i].to]=1; pre[edge[i].to]=x; if(!ma[edge[i].to]) { int k,j; for(j=x,i=edge[i].to; j; j=pre[i=k]) { k=ma[j]; ma[i]=j; ma[j]=i; } return 1; } st[ma[edge[i].to]]=0; q.push(ma[edge[i].to]); } else if(fa[edge[i].to]!=fa[x]&&!st[edge[i].to]) { lca=get_lca(edge[i].to,x); up(edge[i].to,x); up(x,edge[i].to); for(int j=1; j<=n+3*m; j++) { fa[j]=fa[fa[j]]; } } } } return 0; } void solve() { for(int i=1; i<=n+3*m; i++) { ans+=!ma[i]&&match(i); //cout<<"ok"; } cout

    推荐阅读


    上一篇：iOS-BLE蓝牙开发持续更新

    下一篇：以太坊挖矿软件，以太坊挖矿工具，解密抽水整个过程。