• <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地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久高潮毛片免费全部播放| 久久久久亚洲av成人网人人软件 | 日本久久中文字幕| 久久精品视频91| 少妇无套内谢久久久久| 久久99精品国产麻豆宅宅| 久久久国产乱子伦精品作者| 一本大道加勒比久久综合| 婷婷久久综合九色综合绿巨人| 精品久久久久久国产| 草草久久久无码国产专区| 欧美一区二区久久精品| 久久福利青草精品资源站| 中文字幕精品久久| 99久久国产综合精品五月天喷水| 精产国品久久一二三产区区别 | 久久ZYZ资源站无码中文动漫 | 蜜臀av性久久久久蜜臀aⅴ麻豆 | 国产精品视频久久久| 一本综合久久国产二区| 青青草国产精品久久| 97精品依人久久久大香线蕉97| 国产高清美女一级a毛片久久w| 色婷婷综合久久久久中文一区二区| 久久久精品人妻无码专区不卡| 国内精品久久久久久99蜜桃 | 色婷婷综合久久久中文字幕| 久久久国产视频| 久久久亚洲精品蜜桃臀| 国产精品成人无码久久久久久 | 蜜臀久久99精品久久久久久| 一本大道加勒比久久综合| 久久免费视频观看| 精品免费tv久久久久久久| 国产精品久久久久影视不卡| 国产精品青草久久久久婷婷| 9久久9久久精品| 国产精品久久久久…| 国产高潮久久免费观看| 一级a性色生活片久久无少妇一级婬片免费放| 国产2021久久精品|