1. PTT
  2. Prob_Solve

[問題] 動態圖連通性

作者: FRAXIS (喔喔)   2015-04-04 21:42:36
最近在研究一些動態的問題。
給定一無向圖 G ，設計一個資料結構可以支援加邊、刪邊、判斷兩點是否連通。
http://www.spoj.com/problems/DYNACON2/
有什麼好實作的方法嗎？雖然有很多理論的研究，但是看起來都很複雜。
作者: DJWS (...)   2015-04-05 07:11:00
NOI04的學生報告有一篇有提到 可以用二進位分解要不然就是用 euler tour tree 這個是最好理解的說錯 是NOI14
作者: FRAXIS (喔喔)   2015-04-05 22:10:00
感謝那動態最小生成樹有沒有好實作的解法？
作者: DJWS (...)   2015-04-07 22:43:00
http://www.crcnetbase.com/isbn/9781420035179 chap36
作者: FRAXIS (喔喔)   2015-04-08 00:46:00
http://roosephu.github.io/2013/03/25/dynamic-mst/雖然比較慢 但是好像比較容易作一點
繼續閱讀
Re: [問題] 最大流最小費用問題DJWSRe: [問題] 最大流最小費用問題FRAXISRe: [問題] 最大流最小費用問題DJWSRe: [問題] 最大流最小費用問題DJWSRe: [問題] 最大流最小費用問題saladimRe: [問題] 最大流最小費用問題DJWS[問題] 最大流最小費用問題saladim[問題] image warpingDJWS[問題] 請問這個的時間和空間複雜度illl[問題] 包含 k 點的最小正方形 (平行座標軸)FRAXIS

Links booklink

Contact Us: admin [ a t ] ucptt.com