The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

whu 带花树算法 template ,研究下..

struct Graph {
    
int n, match[maxn];
    
bool adj[maxn][maxn];
    
void clear() {
        memset(adj, 
0sizeof(adj));
        n 
= 0;
    }

    
void insert(const int &u, const int &v) {
        get_max(n, max(u, v) 
+ 1);
        adj[u][v] 
= adj[v][u] = 1;
    }

    
int max_match() {
        memset(match, 
-1sizeof(match));
        
int ans = 0;
        
for (int i = 0; i < n; ++i) {
            
if (match[i] == -1{
                ans 
+= bfs(i);
            }

        }

        
return ans;
    }

    
int Q[maxn], pre[maxn], base[maxn];
    
bool hash[maxn];
    
bool in_blossom[maxn];
    
int bfs(int p) {
        memset(pre, 
-1sizeof(pre));
        memset(hash, 
0sizeof(hash));
        
for (int i = 0; i < n; ++i) {
            
base[i] = i;
        }

        Q[
0= p;
        hash[p] 
= 1;
        
for (int s = 0, t = 1; s < t; ++s) {
            
int u = Q[s];
            
for (int v = 0; v < n; ++v) {
                
if (adj[u][v] && base[u] != base[v] && v != match[u]) {
                    
if (v == p || (match[v] != -1 && pre[match[v]] != -1)) {
                        
int b = contract(u, v);
                        
for (int i = 0; i < n; ++i) {
                            
if (in_blossom[base[i]]) {
                                
base[i] = b;
                                
if (hash[i] == 0{
                                    hash[i] 
= 1;
                                    Q[t
++= i;
                                }

                            }

                        }

                    }
 else if (pre[v] == -1{
                        pre[v] 
= u;
                        
if (match[v] == -1{
                            argument(v);
                            
return 1;
                        }
 else {
                            Q[t
++= match[v];
                            hash[match[v]] 
= 1;
                        }

                    }

                }

            }

        }

        
return 0;
    }

    
void argument(int u) {
        
while (u != -1{
            
int v = pre[u];
            
int k = match[v];
            match[u] 
= v;
            match[v] 
= u;
            u 
= k;
        }

    }

    
void change_blossom(int b, int u) {
        
while (base[u] != b) {
            
int v = match[u];
            in_blossom[
base[v]] = in_blossom[base[u]] = true;
            u 
= pre[v];
            
if (base[u] != b) {
                pre[u] 
= v;
            }

        }

    }

    
int contract(int u, int v) {
        memset(in_blossom, 
0sizeof(in_blossom));
        
int b = find_base(base[u], base[v]);
        change_blossom(b, u);
        change_blossom(b, v);
        
if (base[u] != b) {
            pre[u] 
= v;
        }

        
if (base[v] != b) {
            pre[v] 
= u;
        }

        
return b;
    }

    
int find_base(int u, int v) {
        
bool in_path[maxn] = {};
        
while (true{
            in_path[u] 
= true;
            
if (match[u] == -1{
                
break;
            }

            u 
= base[pre[match[u]]];
        }

        
while (!in_path[v]) {
            v 
= base[pre[match[v]]];
        }

        
return v;
    }

}
;

posted on 2010-04-24 16:43 abilitytao 阅读(752) 评论(2)  编辑 收藏 引用

评论

# re: whu 带花树算法 template ,研究下.. 2010-12-16 20:41 研究下

带权的话,怎么修改?  回复  更多评论   

# re: whu 带花树算法 template ,研究下.. 2011-02-23 12:07 tw

你好,请问base数组干什么用的吗?  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理