@GooLu:Hello,这其实是菌阁的“文化”吧,是阁人、术士歌颂赞扬九位强者的。至于祭礼,菌阁不会举行祭礼,这属于“追随者”们自发的赞颂和传播。
九歌·菌阁·古音短祀3个月前
喵的高中真的好大怨气
长夜鬼1年前
梦开始的地方啊,虽然还只是抄抄百科。
PWN环境配置3年前
逛代码看了一遍,算法本身倒是没什么大问题,排序、并查集、路径压缩都有,基本的 Kruskal 实现是正确的。
不过问题也不少,我纠正一下。
首先是完全没有考虑图不连通的情况。程序只管把能选的边选出来,最后直接输出 `ans`,至于有没有成功构造出最小生成树,根本不检查。
其次,`ans` 用的是 `int`,边权稍微大一点就有整数溢出的风险。并查集合并也只是简单地 `f[fx] = fy`,没有按秩合并或按大小合并。
还有那个 `maxn = 1e6 + 10`,不管输入规模多大,都先把整个并查集数组初始化一遍。虽然算不上什么严重问题,但确实比较粗糙。
不过问题也不少,我纠正一下。
首先是完全没有考虑图不连通的情况。程序只管把能选的边选出来,最后直接输出 `ans`,至于有没有成功构造出最小生成树,根本不检查。
其次,`ans` 用的是 `int`,边权稍微大一点就有整数溢出的风险。并查集合并也只是简单地 `f[fx] = fy`,没有按秩合并或按大小合并。
还有那个 `maxn = 1e6 + 10`,不管输入规模多大,都先把整个并查集数组初始化一遍。虽然算不上什么严重问题,但确实比较粗糙。
Kruskal 算法3年前
相比 Kruskal,这份 Prim 的问题就明显多了。
最扎眼的应该是 `const int inf = 9999`。当年随手定义了一个无穷大,实际上只要边权达到 9999,就可能出现找不到下一个顶点的情况。
更离谱的是 `int minn,pos;`,其中 `pos` 根本没有初始化。如果图不连通,或者所有候选边权都不小于 `inf`,程序就可能直接拿一个未初始化的变量去访问数组,属于未定义行为。
还有 `maps[6000][6000]` 这个邻接矩阵,光是它就占了大约 144 MB 内存。对于稀疏图,这种存储方式显然不太合适。而且数组下标从 1 开始使用,如果 `n` 真等于 6000,还会发生越界。
`main()` 里面甚至留了一个完全没有使用的 `minIndex`,估计是写到一半改过思路,最后也没清理。
不过算法的主体逻辑倒是没有写错。通过 `dis[]` 维护当前生成树到其他顶点的最小连接权值,再不断加入新的顶点,确实是朴素 Prim 的正常实现。
最扎眼的应该是 `const int inf = 9999`。当年随手定义了一个无穷大,实际上只要边权达到 9999,就可能出现找不到下一个顶点的情况。
更离谱的是 `int minn,pos;`,其中 `pos` 根本没有初始化。如果图不连通,或者所有候选边权都不小于 `inf`,程序就可能直接拿一个未初始化的变量去访问数组,属于未定义行为。
还有 `maps[6000][6000]` 这个邻接矩阵,光是它就占了大约 144 MB 内存。对于稀疏图,这种存储方式显然不太合适。而且数组下标从 1 开始使用,如果 `n` 真等于 6000,还会发生越界。
`main()` 里面甚至留了一个完全没有使用的 `minIndex`,估计是写到一半改过思路,最后也没清理。
不过算法的主体逻辑倒是没有写错。通过 `dis[]` 维护当前生成树到其他顶点的最小连接权值,再不断加入新的顶点,确实是朴素 Prim 的正常实现。
Prim 算法3年前
@神奇菌:这是亲闺女!
神奇菌的诞生4年前
喜大奔波
ACE 149分高分通过!!!
HCIP 三门都在900高分通过!!!
我真牛逼!
ACE 149分高分通过!!!
HCIP 三门都在900高分通过!!!
我真牛逼!
曾经打败我的力量,终将被我掌握,班徽用CDR做的!我做的!
CDR10年前
没有更多啦












