• o Edmonds' blossom-contraction 算法
  
  
   次小生成樹(shù)(K小生成樹(shù))
  最小樹(shù)形圖
   最小K限制度生成樹(shù)
   最優(yōu)比率生成樹(shù)(0-1分?jǐn)?shù)規(guī)劃)
  第K最短路
  LP問(wèn)題以及Primal-Dual(單純型法)
   最大流(最短增廣路、最高標(biāo)號(hào)預(yù)流推進(jìn))
   最小費(fèi)用流(最小費(fèi)用路、Primal-Dual算法)
   二分圖最優(yōu)匹配(原始-對(duì)偶KM算法)
  

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

最短路 
 
1062(cut 建模的時(shí)侯要注意 ，不斷建符合等級(jí)差的圖 做最短路徑)
 
1125（cut 做全源最短路
   再對(duì)以每各點(diǎn)為根的樹(shù)：找最長(zhǎng)的邊
 再對(duì)每棵樹(shù)的最長(zhǎng)邊 找最短的那一條  
 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
    起點(diǎn)到n點(diǎn) 路徑上  所能承受的 最大重量的車
      
    dist[k]   源點(diǎn)到k 路徑中最小的那個(gè)邊權(quán)值   mat[k][i]邊k-i權(quán)值 
   取路徑 dist[k]  和mat【k】【i】邊最大那個(gè)  更新 dist[i]  )
 
2253(cut 要求的與 1797相反)

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