• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            


            The Fourth Dimension Space
            

            枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安； 不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！  -如夢令
            

            




            
	
					
	
            
		
            
			whu 帶花樹算法 template ，研究下..
		
            
		
            struct Graph {
                            int n, match[maxn];
                            bool adj[maxn][maxn];
                            void clear() {
                    memset(adj,             0, sizeof(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,             -1, sizeof(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,             -1, sizeof(pre));
                    memset(hash,             0, sizeof(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,             0, sizeof(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 閱讀(863) 評論(2)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

            評論
            
	
	
			
            
				# re: whu 帶花樹算法 template ，研究下..
					
						2010-12-16 20:41
					
				研究下
			
            
			
            
				帶權的話，怎么修改？  回復  更多評論
				  
			
            
		
			
            
				# re: whu 帶花樹算法 template ，研究下..
					
						2011-02-23 12:07
					
				tw
			
            
			
            
				你好，請問base數組干什么用的嗎？  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



久久午夜无码鲁丝片秋霞|
国产精品视频久久久|
久久青青草视频|
久久综合亚洲欧美成人|
91久久精品国产免费直播|
思思久久99热免费精品6|
久久精品中文无码资源站|
久久精品国产只有精品66|
久久棈精品久久久久久噜噜|
国产三级精品久久|
欧美亚洲国产精品久久|
国产美女久久久|
久久99这里只有精品国产|
午夜不卡888久久|
久久人人爽爽爽人久久久|
欧美伊人久久大香线蕉综合69|
精品久久久久久久无码|
囯产极品美女高潮无套久久久
|
亚洲精品高清一二区久久|
久久99精品国产麻豆|
亚洲综合精品香蕉久久网|
久久婷婷五月综合成人D啪|
日本三级久久网|
久久ZYZ资源站无码中文动漫|
伊人久久大香线蕉综合网站|
国产成人久久久精品二区三区|
欧洲精品久久久av无码电影|
久久久久久精品无码人妻|
久久亚洲精品无码播放|
久久精品亚洲乱码伦伦中文|
好久久免费视频高清|
99国产精品久久久久久久成人热|
亚洲狠狠婷婷综合久久久久|
人妻丰满AV无码久久不卡
|
亚洲精品无码久久久久去q|
亚洲国产精品无码久久久久久曰|
亚洲午夜精品久久久久久人妖|
中文字幕亚洲综合久久|
99久久精品无码一区二区毛片|
91麻豆精品国产91久久久久久
|
久久成人国产精品|