圖論

• [圖論]pku3417      摘要: 我的做法是，對于每條新邊，記錄樹中與之對應的路徑。然后對于每條樹邊，統(tǒng)計被對應的次數。最后記錄每個點到樹根的路徑上，有多少個1（設為q[i]）。對于新邊(x,y)，它對答案的貢獻就是q[x] + q[y] - 2q[lca(x,y)]。除了這些，答案還應加上樹中0邊的數量 * m。
  
    閱讀全文
  posted @ 2007-10-06 20:53 Felicia 閱讀(526) | 評論 (0)  編輯
• [圖論][zz]給出一個沒有偶圈的簡單無向圖，求兩個頂點間路徑的數目      摘要: 給出一個沒有偶圈的簡單無向圖，求兩個頂點間路徑的數目
  
    閱讀全文
  posted @ 2007-09-19 10:08 Felicia 閱讀(1020) | 評論 (2)  編輯
• [圖論]pku1125      摘要: 簡單題。很早以前做的。貼一下凌亂的代碼。
  
    閱讀全文
  posted @ 2007-09-02 20:09 Felicia 閱讀(521) | 評論 (2)  編輯
• [圖論]最大流(類實現)      摘要: 復雜度 O(n^2m)。支持一邊構建網絡，一邊求最大流。每次調用 flow()，得到當前新增的流量。
  
    閱讀全文
  posted @ 2007-08-13 21:12 Felicia 閱讀(1038) | 評論 (1)  編輯
• 單源最短路 Dijkstra O(mlogn) (類實現)      摘要: 單源最短路 Dijkstra O(mlogn) (類實現)
  
    閱讀全文
  posted @ 2007-08-13 10:01 Felicia 閱讀(848) | 評論 (1)  編輯
• 二分圖最大匹配(類實現)      摘要: 二分圖最大匹配(類實現)
  
    閱讀全文
  posted @ 2007-08-11 21:30 Felicia 閱讀(1248) | 評論 (0)  編輯