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