• <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>
            我要啦免费统计
            * 求有向圖的強連通分支 (Strongerst Connected Component)(cut)
            o Kosaraju算法  
            o Gabow算法
            o Tarjan算法
            * 求最小生成樹 (Minimal Spanning Trees) (cut)
            o Kruskal算法(cut邊更新)
            o Prim算法(cut點更新)
            * 最短路徑問題(cut)
            o SSSP(Single-source Shortest Paths)
            * Dijkstra算法  (cut)
            * Bellman-Ford算法(SPFA算法)(cut)
            o APSP(All-pairs Shortest Paths)
            * Floyd-Warshall算法(cut)
            * Johnson算法
            * 網(wǎng)絡(luò)流問題     
            o 最大網(wǎng)絡(luò)流
            * 增廣路算法
            * Ford-Fulkerson算法
            * Edmonds-Karp算法
            * Dinic
            * 預(yù)流推進算法
            o 最小費用流
            * 圖匹配問題  (部分cut)
            o 匈牙利算法(cut)
            o Kuhn-Munkres算法
            • o Edmonds' blossom-contraction 算法


               次小生成樹(K小生成樹)
              最小樹形圖
               最小K限制度生成樹
               最優(yōu)比率生成樹(0-1分數(shù)規(guī)劃)
              第K最短路
              LP問題以及Primal-Dual(單純型法)
               最大流(最短增廣路、最高標號預(yù)流推進)
               最小費用流(最小費用路、Primal-Dual算法)
               二分圖最優(yōu)匹配(原始-對偶KM算法)


            acm.pku.edu.cn 的:
            最小生成樹  
            1251(cut)
             
            1258(cut)
             
            1789(cut)
             
            2485(cut)

            最短路 
             
            1062(cut 建模的時侯要注意 ,不斷建符合等級差的圖 做最短路徑)
             
            1125(cut 做全源最短路
               再對以每各點為根的樹:找最長的邊
             再對每棵樹的最長邊 找最短的那一條  
             int ans=maxint;
                for(i=1;i<=n;i++){
                  tmp=-1;
                   for(j=1;j<=n;j++){
                      tmp=max(tmp,a[i][j]);             
                   }
                   if(tmp < ans){ans=tmp;val=i;}
                }

             
            1797(cut
                起點到n點 路徑上  所能承受的 最大重量的車
                  
                dist[k]   源點到k 路徑中最小的那個邊權(quán)值   mat[k][i]邊k-i權(quán)值 
               取路徑 dist[k]  和mat【k】【i】邊最大那個  更新 dist[i]  )
             
            2253(cut 要求的與 1797相反)




            Johnson算法適用于求All Pairs Shortest Path. Johnson算法應(yīng)用了重標號技術(shù),先進行一次Bellman-Ford算法,然后對原圖進行重標號,w'(i,j)=h[i]-h[j]+w(i,j)。然后對每個點進行一次Dijkstra,每次Dijkstra的復雜度為O(nlogn+m),于是算法復雜度為O(n^2logn+m)。


             

            posted on 2008-10-26 23:33 閱讀(1016) 評論(3)  編輯 收藏 引用 所屬分類: algorithm

            評論:
            # re: 圖算法進度 2008-11-20 11:13 | 868
            hi  回復  更多評論
              
            # re: 圖算法進度 2009-08-26 11:48 | 學習中
            我在網(wǎng)上搜不到最小費用的Primal Dual算法

            大哥能否給一個  回復  更多評論
              
            # re: 圖算法進度 2009-09-22 10:44 | cdy20
            @學習中

            T_T!! 百度很多。。。。
              回復  更多評論
              
            无码人妻少妇久久中文字幕| 亚洲欧美国产日韩综合久久| 久久人人爽人人爽人人片AV不| 久久久精品人妻一区二区三区四| 久久综合给合久久狠狠狠97色 | 久久久久久一区国产精品| 国产无套内射久久久国产| 一本久道久久综合狠狠躁AV| 久久精品无码午夜福利理论片| 91精品国产综合久久四虎久久无码一级 | 亚洲精品tv久久久久久久久| 久久er国产精品免费观看2| 久久综合九色综合欧美就去吻| 浪潮AV色综合久久天堂| 久久精品国产99久久香蕉| 久久99精品久久只有精品| 亚洲国产成人久久综合野外| 国产精品久久免费| 东方aⅴ免费观看久久av| 久久高清一级毛片| 久久久久久久久久久久中文字幕| 亚洲AⅤ优女AV综合久久久| 亚洲国产精品人久久| 精品少妇人妻av无码久久| 久久午夜免费视频| 久久精品国产一区二区电影| 99精品国产在热久久无毒不卡| 久久只有这里有精品4| 久久久久久久综合综合狠狠| 国产毛片久久久久久国产毛片 | 久久精品亚洲男人的天堂| 精品久久久久久亚洲| 国产亚洲精品自在久久| 久久久久久伊人高潮影院| 亚洲AⅤ优女AV综合久久久| 久久精品国产亚洲av瑜伽| 99久久夜色精品国产网站| 丁香五月综合久久激情| 伊人久久大香线焦综合四虎| 岛国搬运www久久| 国产精品丝袜久久久久久不卡|