• <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>
            付翔的專欄
            在鄙視中成長 記錄成長的點滴
            posts - 106,  comments - 32,  trackbacks - 0

            這道題 就是利用匈牙利算法 然后將問題轉(zhuǎn)化為 最大匹配問題 view plaincopy to clipboardprint?
            #include  <iostream>   
             

            const   int   MaxN = 500 + 1;   
            bool   map[MaxN][MaxN] , ck[MaxN];   
            int     n , match[MaxN] , max_match , k;    
            bool  search(int x)   
            {   
                  
            int i , t;   
                  
            for (i = 1 ; i <= n ; i ++)   
                  
            if (map[i][x]&&!ck[i])   
                  
            {   
                      ck[i] 
            = true;   
                      t 
            = match[i];   
                      match[i] 
            = x;   
                      
            if (t ==0 || search(t)) return true;   
                      match[i] 
            = t;                              
                  }
               
                  
            return false;         
            }
               
            void  hungary()   
            {   
                  
            int  i ;   
                  memset(match , 
            0 , sizeof(match));   
                  max_match 
            = 0;   
                  
            for ( i = 1 ; i <= n ; i ++)   
                  
            {   
                     memset(ck , 
            false , sizeof(ck));   
                     
            if (search(i)) max_match++;   
                  }
                     
            }
               
            int   main()   
            {   
                    
                  
            int i  , x , y;   
                  scanf(
            "%d%d",&n,&k);   
                  
            for ( i = 1 ; i <= k ; i++)   
                  
            {   
                          scanf(
            "%d%d",&x,&y);   
                          map[x][y] 
            = true;   
                  }
               
                  hungary();   
                  printf(
            "%d\n",max_match);    
                     
                  
            return 0;         
            }
              
            #include  
            <iostream>

            const   int   MaxN = 500 + 1;
            bool   map[MaxN][MaxN] , ck[MaxN];
            int     n , match[MaxN] , max_match , k; 
            bool  search(int x)
            {
                  
            int i , t;
                  
            for (i = 1 ; i <= n ; i ++)
                  
            if (map[i][x]&&!ck[i])
                  
            {
                      ck[i] 
            = true;
                      t 
            = match[i];
                      match[i] 
            = x;
                      
            if (t ==0 || search(t)) return true;
                      match[i] 
            = t;                           
                  }

                  
            return false;      
            }

            void  hungary()
            {
                  
            int  i ;
                  memset(match , 
            0 , sizeof(match));
                  max_match 
            = 0;
                  
            for ( i = 1 ; i <= n ; i ++)
                  
            {
                     memset(ck , 
            false , sizeof(ck));
                     
            if (search(i)) max_match++;
                  }
                  
            }

            int   main()
            {
                 
                  
            int i  , x , y;
               scanf(
            "%d%d",&n,&k);
                  
            for ( i = 1 ; i <= k ; i++)
                  
            {
                          scanf(
            "%d%d",&x,&y);
                          map[x][y] 
            = true;
                  }

                  hungary();
                  printf(
            "%d\n",max_match); 
                  
                  
            return 0;      
            }

             

             

             完全是 模板的套用 呵呵


             

            posted on 2009-08-04 17:05 付翔 閱讀(932) 評論(0)  編輯 收藏 引用

            <2011年7月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            日本亚洲色大成网站WWW久久| 久久久久成人精品无码中文字幕| 欧美久久精品一级c片片| 国产91色综合久久免费分享| 99久久国产热无码精品免费久久久久| 久久99亚洲综合精品首页| 国内精品伊人久久久影院| 精品国产一区二区三区久久| 久久久久一本毛久久久| 亚洲综合熟女久久久30p| 久久免费视频观看| 亚洲国产精品无码成人片久久| 久久综合九色综合精品| 久久国产色av免费看| 国内精品久久久久久麻豆| 一本色道久久HEZYO无码| 久久久亚洲精品蜜桃臀| 国产一级做a爰片久久毛片| 一本一本久久A久久综合精品| 久久99精品国产麻豆不卡| 久久男人Av资源网站无码软件| 久久人妻少妇嫩草AV无码蜜桃| 国内精品人妻无码久久久影院 | 青青草原综合久久大伊人导航 | 久久精品国产亚洲7777| 人妻精品久久无码区| 色播久久人人爽人人爽人人片AV| 精品久久人人做人人爽综合| 久久精品毛片免费观看| 久久无码人妻一区二区三区午夜| 国产69精品久久久久观看软件| 久久久久久亚洲精品无码| www亚洲欲色成人久久精品| 99精品国产在热久久无毒不卡| 狠狠色综合网站久久久久久久高清 | 丁香五月综合久久激情| 久久久久四虎国产精品| 色综合久久综精品| 精品免费久久久久国产一区| 国产成人久久精品激情| 亚洲国产二区三区久久|