UOJ79 一般图最大匹配
题目描述
从前一个和谐的班级,所有人都是搞OI的。有 nn 个是男生,有 00 个是女生。男生编号分别为 1,…,n1,…,n。
现在老师想把他们分成若干个两人小组写动态仙人掌,一个人负责搬砖另一个人负责吐槽。每个人至多属于一个小组。
有若干个这样的条件:第 vv 个男生和第 uu 个男生愿意组成小组。
请问这个班级里最多产生多少个小组?
输入格式
第一行两个正整数,n,mn,m。保证 n≥2n≥2。
接下来 mm 行,每行两个整数 v,uv,u 表示第 vv 个男生和第 uu 个男生愿意组成小组。保证 1≤v,u≤n1≤v,u≤n,保证 v≠uv≠u,保证同一个条件不会出现两次。
输出格式
第一行一个整数,表示最多产生多少个小组。
接下来一行 nn 个整数,描述一组最优方案。第 vv 个整数表示 vv 号男生所在小组的另一个男生的编号。如果 vv 号男生没有小组请输出 00。
样例一
input
10 20
9 2
7 6
10 8
3 9
1 10
7 1
10 9
8 6
8 2
8 1
3 1
7 5
4 7
5 9
7 8
10 4
9 1
4 8
6 3
2 5
output
5
9 5 6 10 2 3 8 7 1 4
样例二
input
5 4
1 5
4 2
2 1
4 3
output
2
2 1 4 3 0
正解:带花树算法
解题报告:
这道题是一般图最大匹配,也就是带花树算法裸题。
大概讲一下一般图最大匹配的思想:一般图最大匹配由带花树算法实现,2015年国家集训队论文中我校学长陈胤伯详细介绍了这一算法。
考虑一般图与二分图最大的不同就在于一般图存在奇环,所以我们不能完全套用二分图最大匹配的算法。
在这里不加以证明的给出具体做法(证明详见2015年国家队论文):
每次从一个未盖点出发,将其命名为偶点(偶点匹配的点称之为奇点),枚举其出边以及出边连接的点v:
如果v在本次BFS中还未被经过,则假设未匹配,那么找到了一条增广路,原路返回,把原来的匹配边和非匹配边取反,这样可以使答案加一;否则,将v的匹配点加入队列中拓展,根据我们上面的定义,v的匹配点显然也是偶点。
如果v已经访问过,那么显然出现了环,这个环如果是偶环则不用考虑,如果是奇环且本身两个点就不处在同一个现有已经处理过的奇环中,我们就需要将其缩为一个点(或者说是一朵花),并且把上面的奇点全都标记为偶点,丢到队列里面拓展。
这就是带花树的完整做法。不理解的可以结合我的代码理解一下。我就是看别人代码看懂的......
代码如下:
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 520;
const int MAXM = 250011;
const int MAXL = 10011;
int n,m,ecnt,first[MAXN],next[MAXM],to[MAXM],father[MAXN],Tim;
int dui[MAXL],head,tail,id[MAXN],pre[MAXN],match[MAXN],ans,vis[MAXN];
inline int find(int x){ if(father[x]!=x) father[x]=find(father[x]); return father[x]; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
} inline int lca(int x,int y){
Tim++;
while(vis[x]!=Tim) {
if(x) {
x=find(x);
if(vis[x]==Tim) return x;
vis[x]=Tim;
if(match[x]!=0) x=find(pre[match[x]]);
else x=0;
}
swap(x,y);
}
return x;
} inline void change(int x,int y,int k){//把奇环上的点缩成一个点,并且把原来是奇点的点变成偶点,加入队列
while(find(x)!=k) {
pre[x]=y; int z=match[x];
if(id[z]==1) { id[z]=0; dui[++tail]=z; }
if(find(z)==z) father[z]=k;
if(find(x)==x) father[x]=k;
y=z; x=pre[y];
}
} inline bool bfs(int ini){
for(int i=1;i<=n;i++) id[i]=-1,father[i]=i;
head=tail=0; dui[++tail]=ini; id[ini]=0; int u;
while(head<tail) {
u=dui[++head];
for(int i=first[u];i;i=next[i]) {
int v=to[i];
if(id[v]==-1) {
pre[v]=u; id[v]=1;
if(!match[v]) {
int last,t,now=v;
while(now!=0) {
t=pre[now]; last=match[t];
match[t]=now; match[now]=t;
now=last;
}
return true;
}
id[match[v]]=0; dui[++tail]=match[v];
}
else if(id[v]==0&&find(u)!=find(v)){ //出现奇环且不是在同一个环中
int g=lca(u,v);
change(u,v,g);
change(v,u,g);
}
}
}
return false;
} inline void work(){
n=getint(); m=getint(); int x,y;
for(int i=1;i<=m;i++) {
x=getint(); y=getint();
next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y;
next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x;
}
for(int i=1;i<=n;i++) if(!match[i]&&bfs(i)) ans++;
printf("%d\n",ans);
for(int i=1;i<=n;i++) printf("%d ",match[i]);
} int main()
{
work();
return 0;
}
最新文章
- 解决web中的乱码
- sharepoint2010问卷调查(3)-实现问卷的开始和结束时间(采用自定义字段类型)
- python递归次数和堆栈溢出问题
- memcpy 和直接赋值的性能差异
- 【wikioi】1229 数字游戏(dfs+水题)
- Scrum会议5(Beta版本)
- 【题解】【数组】【Prefix Sums】【Codility】Passing Cars
- JavaScript中的Function(函数)对象
- validate方法配置项
- MyFirstStruts2
- stark组件之展示数据(查)
- mysql 定期删除表中无用数据
- Erlang ETS Table
- db2常见命令
- go标准库-log包源码学习
- RelativeLayout 相对布局
- controlfile作为RMAN的repository时,对 keep time 的测试
- day6:vcp考试
- 洛谷 P1783 海滩防御 解题报告
- 20165230 《Java程序设计》实验四 Android程序设计实验报告
热门文章
- JavaMail发送邮件第一版
- 使input文本框随其中内容而变化长度的方法
- jQuery选择什么版本 1.x? 2.x? 3.x?
- infopath发布的提示“无法解析SOAP消息”(The SOAP message cannot be parsed)问题解决方案
- Mac OS X中bogon的处理
- Redis五种基本数据结构
- 从Sql Server表中随机获取一些记录最简单的方法
- SQL Server 2012新增和改动DMV
- ubuntu安装pppoeconf后与networkmanager冲突
- Shell教程