圖論

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