邻接表直接记忆化dfsAC

Thanks voyagec2 牛 的提示.

归来归去多麻烦,直接记忆DFS吧

无解的特征是DFS深度>N

日日的一开始一直FOR I:=1 TO N DO READ(X,Y,K);

无限0分

我们将相等的结点放在一个集合里，然后根据点之间的关系确定集合之间的关系，再通过topo排序求出最长路径。

先做一次处理，把所有相等的点归为一点，把这些大点构新图求最长路，用DFS即可

（枚举入度为0的点，如果搜索中发现回路，输出‘NO’）输出最长路。

我半秃

这个题最关键的是处理等于的情况，我们可以这样处理，比如 a=b 因为a,b各自都会有一个和别的点的关系，所以我们就把这连个点的关系合并，也就是说a如果可以连接i，而b不可以，那么就让b也可以连接i,转换后的图就变成了我们熟悉的可以用拓扑解决的问题了，剩下的就是拓扑排序了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

1、第3、5个点有自环！崩死我了……

2、拓扑的时候先把所有

想了一个利用FLoyed的方法，结果超时

floyed真是不能乱用

并查+拓扑

单拓扑也是可以的.

但相对不容易编..

要程序参考的请到我空间..http://user.qzone.qq.com/69789166/blog/1224044820

希望大家能够自己先做,实在不行再参考.

[1]按照相等关系刷顶点

[2]TopSort

。

谁说说到底怎么处理好多点归为一个点的啊。。。

数据弱到家

本来想试验一下不写SPFA或者BELLMAN能那多少

只判断度数来是否有环 竟然A了。。。

最好再写一个好的判断环的部分

注意图的连通性

终于过了 = =

郁闷..堆栈溢出..改了一个我也不知道为什么要改的地方就过了..1个小时啊..

元谋!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

spfa好强！

O(kn^2)超时，

O(km)9ms。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 41ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：175ms

有点慢哪

把max写的min,郁闷了我40+分钟~底歇！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

好题。

我是用并查集+拓扑排序AC的，谢谢大家

可以把相等的点都缩成一个,然后在拓扑排序的时候看看总共进行了几次就是答案