首页 > 代码库 > [kuangbin带你飞]专题十 匹配问题 一般图匹配
[kuangbin带你飞]专题十 匹配问题 一般图匹配
过去做的都是二分图匹配 即 同一个集合里的点 互相不联通
但是如果延伸到一般图上去 求一个一般图的最大匹配 就要用带花树来解决
带花树模板 用来处理一个无向图上的最大匹配
看了一会还是不懂 抄了一遍kuangbin的模板熟悉了一下
还有一个一般图最大权匹配 保存下来了VFK菊苣的模板题代码当作板子 http://uoj.ac/submission/16359
但愿以后的比赛永远也遇不到 .. 遇到了也能抄对 .. 抄错了也能过 ..
R ural1099
kuangbin模板
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n ;
bool g[255][255];
int match[255] ;
bool inque[255] , inpath[255] , inblo[255] ;
int head , tail ;
int que[255] ;
int st , fi ;
int newbase ;
int fa[255] , base[255] ;
int cnt ;
void creag(){
int u ,v ;
memset(g , false , sizeof(g)) ;
scanf("%d",&n ) ;
while(scanf("%d%d" , &u , &v) !=EOF){
g[u][v] = g[v][u] = true ;
}
}
void push(int u){
que[tail] = u ;
tail ++ ;
inque[u] = true ;
}
int pop(){
int res = que[head] ;
head ++ ;
return res ;
}
int findca(int u , int v) {
memset(inpath , false , sizeof(inpath)) ;
while(true){
u = base[u];
inpath[u] = true ;
if(u == st)break;
u = fa[match[u]] ;
}
while(true){
v = base[v] ;
if(inpath[v])break;
v = fa[match[v]] ;
}
return v ;
}
void reset(int u ){
int v ;
while(base[u] != newbase ){
v = match[u];
inblo[base[u]] = inblo[base[v]] = true ;
u = fa[v] ;
if(base[u] != newbase )fa[u] = v;
}
}
void blocon(int u , int v ){
newbase = findca(u,v);
memset(inblo , false , sizeof(inblo)) ;
reset(u) ;
reset(v) ;
if(base[u] != newbase )fa[u] = v ;
if(base[v] != newbase )fa[v] = u ;
for(int tu = 1 ;tu <= n ; tu ++ ){
if(inblo[base[tu]]){
base[tu] = newbase ;
if(!inque[tu] )push(tu ) ;
}
}
}
void findatp(){
memset(inque , false , sizeof(inque)) ;
memset(fa , 0 , sizeof(fa)) ;
for(int i = 1; i <= n ; i ++ ){
base[i] = i ;
}
head = tail = 1 ;
push(st) ;
fi = 0 ;
while(head < tail ){
int u = pop() ;
for(int v = 1; v <= n ; v ++ ){
if(g[u][v] && (base[u] != base[v] ) && (match[u ] != v)){
if((v == st) || ((match[v] > 0) && fa[match[v]] > 0) ){
blocon(u,v);
}
else if (fa[v] == 0) {
fa[v] = u ;
if(match[v] > 0) {
push(match[v]) ;
}
else {
fi = v ;
break ;
}
}
}
}
}
}
void ap(){
int u ,v , w ;
u = fi ;
while(u > 0) {
v = fa[u] ;
w = match[v] ;
match[v] = u ;
match[u] = v;
u = w ;
}
}
void edmonds (){
memset(match , 0 ,sizeof(match)) ;
for(int u = 1; u <= n; u ++ ){
if(match[u] == 0) {
st = u ;
findatp() ;
if(fi > 0){
ap() ;
}
}
}
}
void print(){
cnt = 0;
for(int u = 1; u <= n ; u ++ ){
if(match[u] > 0)cnt ++ ;
}
printf("%d\n",cnt);
for(int u = 1; u <= n ; u ++ ){
if(u < match[u]) {
printf("%d %d\n",u , match[u]) ;
}
}
}
int main(){
creag();
edmonds() ;
print() ;
}
S hdu4687
给出一群pair 输出那些 不在任何最大匹配中的pair 的编号
不在任何最大匹配的pair 只能是 它的两个端点上 都有必选的pair 所以这个pair不能做相邻pair的替代 因为如果替代 另一个端点上的pair就不能选了
所以 枚举每条边 把这条边的两个端点上的所以边都去掉 如果损失了两个匹配 那么这条边就不在任何一个匹配中
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , m ;
bool g[255][255];
int match[255] ;
bool inque[255] , inpath[255] , inblo[255] ;
int head , tail ;
int que[255] ;
int st , fi ;
int newbase ;
int fa[255] , base[255] ;
int cnt ;
int input[255][2] ;
int output[255] ;
bool bf[255][255] ;
void creag(){
int u ,v ;
memset(g , false , sizeof(g)) ;
memset(bf , false , sizeof(bf)) ;
for(int i = 1; i <= m ; i ++ ){
scanf("%d%d",&u,&v);
g[u][v] = g[v][u] = true ;
bf[u][v] = bf[v][u] = true ;
input[i][0] = u ;
input[i][1] = v ;
}
}
void push(int u){
que[tail] = u ;
tail ++ ;
inque[u] = true ;
}
int pop(){
int res = que[head] ;
head ++ ;
return res ;
}
int findca(int u , int v) {
memset(inpath , false , sizeof(inpath)) ;
while(true){
u = base[u];
inpath[u] = true ;
if(u == st)break;
u = fa[match[u]] ;
}
while(true){
v = base[v] ;
if(inpath[v])break;
v = fa[match[v]] ;
}
return v ;
}
void reset(int u ){
int v ;
while(base[u] != newbase ){
v = match[u];
inblo[base[u]] = inblo[base[v]] = true ;
u = fa[v] ;
if(base[u] != newbase )fa[u] = v;
}
}
void blocon(int u , int v ){
newbase = findca(u,v);
memset(inblo , false , sizeof(inblo)) ;
reset(u) ;
reset(v) ;
if(base[u] != newbase )fa[u] = v ;
if(base[v] != newbase )fa[v] = u ;
for(int tu = 1 ;tu <= n ; tu ++ ){
if(inblo[base[tu]]){
base[tu] = newbase ;
if(!inque[tu] )push(tu ) ;
}
}
}
void findatp(){
memset(inque , false , sizeof(inque)) ;
memset(fa , 0 , sizeof(fa)) ;
for(int i = 1; i <= n ; i ++ ){
base[i] = i ;
}
head = tail = 1 ;
push(st) ;
fi = 0 ;
while(head < tail ){
int u = pop() ;
for(int v = 1; v <= n ; v ++ ){
if(g[u][v] && (base[u] != base[v] ) && (match[u ] != v)){
if((v == st) || ((match[v] > 0) && fa[match[v]] > 0) ){
blocon(u,v);
}
else if (fa[v] == 0) {
fa[v] = u ;
if(match[v] > 0) {
push(match[v]) ;
}
else {
fi = v ;
break ;
}
}
}
}
}
}
void ap(){
int u ,v , w ;
u = fi ;
while(u > 0) {
v = fa[u] ;
w = match[v] ;
match[v] = u ;
match[u] = v;
u = w ;
}
}
void edmonds (){
memset(match , 0 ,sizeof(match)) ;
for(int u = 1; u <= n; u ++ ){
if(match[u] == 0) {
st = u ;
findatp() ;
if(fi > 0){
ap() ;
}
}
}
}
int print(){
int cnt = 0;
for(int u = 1; u <= n ; u ++ ){
if(match[u] > 0 && u < match[u]){
cnt ++ ;
}
}
return cnt ;
}
int main(){
while(scanf("%d%d" , &n, &m )!=EOF){
creag();
edmonds() ;
int res = print() ;
int ans = 0 ;
for(int i = 1; i <= m; i ++ ){
int u = input[i][0] ;
int v = input[i][1] ;
for(int k = 1; k <= n ; k ++ ){
for(int j = 1; j <= n; j ++ )
g[k][j] = bf[k][j] ;
}
for(int j = 1; j <= n ; j ++ ){
g[j][v] = g[v][j] = g[u][j] = g[j][u] = false ;
}
edmonds() ;
int r = print() ;
if(r == res - 2){
ans ++ ;
output[ans] = i ;
}
}
printf("%d\n",ans) ;
for(int i = 1; i <= ans ;i ++ ){
printf("%d",output[i]) ;
if(i != ans)printf(" ") ;
}
printf("\n") ;
}
}
二分图专题总算告一段落了
感觉 现在只会抄模板了 ..
明天...哈理工的最菜的三个选手 我和带我飞我的两个队友要去勇闯ecfinal题了 祝自己好运 ...
[kuangbin带你飞]专题十 匹配问题 一般图匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。