• <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 閱讀(864) 評論(2)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

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

            




            






            

				

            


    
    







            
	   
	



国产精自产拍久久久久久蜜|
久久久久免费精品国产|
亚洲成人精品久久|
99久久精品国产一区二区|
亚洲第一永久AV网站久久精品男人的天堂AV
|
亚洲女久久久噜噜噜熟女|
精品久久久久久亚洲精品|
国产精品欧美久久久久无广告|
久久久无码精品亚洲日韩京东传媒
|
久久乐国产综合亚洲精品|
久久精品国产亚洲av影院|
久久男人AV资源网站|
久久A级毛片免费观看|
天堂无码久久综合东京热|
国产成人久久激情91|
久久这里只有精品首页|
久久久久人妻精品一区三寸蜜桃
|
伊人久久精品线影院|
影音先锋女人AV鲁色资源网久久|
久久国产亚洲精品麻豆|
无遮挡粉嫩小泬久久久久久久
|
99久久精品国内|
狠狠综合久久AV一区二区三区|
久久五月精品中文字幕|
亚洲国产精品久久久久久|
狠狠狠色丁香婷婷综合久久五月
|
久久久免费精品re6|
久久久国产打桩机|
久久天天躁狠狠躁夜夜不卡|
精品久久久久久久久久中文字幕|
国产精品久久久久影院嫩草|
浪潮AV色综合久久天堂|
亚洲av日韩精品久久久久久a|
色99久久久久高潮综合影院|
久久精品国产99久久香蕉|
久久精品国产亚洲5555|
久久精品无码一区二区app|
久久se精品一区精品二区国产|
青青草国产精品久久|
久久精品嫩草影院|
狠狠精品干练久久久无码中文字幕
|