hdu 4514 湫湫系列故事——设计风景线 (无向图并查集判环+非联通图的最长路径)

hdu4514

题意:给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。

思路:无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。

但是需要注意的是。。。题目并没有保证图一定是联通的。。。所以gg了。。

也就是要在一个不联通的图中求最长路径。。。

没想出来。。搜了一下。。有树形dp的做法。。。有并查集的时候带权的做法。。。

不过感觉最容易想到的还是求多次直径的做法。。。

也就是。。每一个联通块求一次直径。。。取最大。。。

具体做的时候。。。加一个bool数组在bfs标记一下就好。。。

以及bfs的时候。。。由于我之后是要得到最大值。。。而图本身可能是不联通的。。所以要注意d数组初始化的问题。。。不能初始化成0x3f…(这么说来即使联通也没必要初始化成0x3f。。。。)

还有一点,这道题数据量比较大。。。用vector存图会MLE …

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz