Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

最小树形图 - riteme.site #74

Open
riteme opened this issue Jun 18, 2018 · 6 comments
Open

最小树形图 - riteme.site #74

riteme opened this issue Jun 18, 2018 · 6 comments
Labels
9b89e7d9152ef5a29a77b21978c539e0 gitment

Comments

@riteme
Copy link
Owner

riteme commented Jun 18, 2018

https://riteme.github.io/blog/2018-6-18/mdst.html
@ghost
Copy link

ghost commented Mar 6, 2019

可是您写的O(ElogV) 版本提交之后超时。。

@ghost
Copy link

ghost commented Mar 6, 2019

我在做某个oj的dmst题目，用的基本的朱刘算法，是超时，不知道有没有更好的优化方法

@ghost
Copy link

ghost commented Mar 6, 2019

而且您写的O（EV）版本，需要800+ms，正常的朱刘只需要100+ms

@riteme
Copy link
Owner Author

riteme commented Mar 7, 2019

@damagegithub
可以提供一下题目吗，其实我也只测了 POJ 那个题，好像数据比较小 qwq

@ghost
Copy link

ghost commented Mar 7, 2019

输入文件 第一行 n m -点，边 n<1000；m<10000
后m行 u v m -边起点 边终点，权重 u，v>1，m<1e9

总是以节点1为根 如果有dmst 输出总权，没有输出no

是学校打acm的测试鸡（国外的）

@ghost
Copy link

ghost commented Mar 7, 2019

如果您愿意，可以微信交流号：damage5211

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
9b89e7d9152ef5a29a77b21978c539e0 gitment
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@riteme