[kuangbin带你飞]专题十匹配问题一般图匹配-白红宇

[kuangbin带你飞]专题十匹配问题一般图匹配

阅读量：5934 次

发布时间：2019-06-19

本文共 5776 字，大约阅读时间需要 19 分钟。

过去做的都是二分图匹配即同一个集合里的点互相不联通

但是如果延伸到一般图上去求一个一般图的最大匹配就要用带花树来解决

带花树模板用来处理一个无向图上的最大匹配

看了一会还是不懂抄了一遍kuangbin的模板熟悉了一下

还有一个一般图最大权匹配保存下来了VFK菊苣的模板题代码当作板子 http://uoj.ac/submission/16359

但愿以后的比赛永远也遇不到 .. 遇到了也能抄对 .. 抄错了也能过 ..

R ural1099

kuangbin模板

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define L long longint 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
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define L long longint 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") ; }}