一拿到这一题什么复杂度都没有分析,直接用floyd做,之后悲催的没有过才想起来有复杂度这回事。之后就考虑用BF来做,wa了几次,主要是因为存边的时候忘写另一半了,也忘更新了,改了之后就过了。时间还可以。之后用spfa来做,是看学姐博客上的,再加一个num[ maxn ]来判断,是否加入队列超过n次,若超过则有负环,但这种用我的代码来实现的话,比较慢。下面给出代码: bellman_ford: #include<cstring> #include<iostream> #include<c…

2014年3月26日 0条评论 0点热度 阅读全文

这题是我第一次用bellman-ford来做题,是我第一次用floyd来处理图的连通性,也是我第一次处理负权的情况,还是我第一次处理环;这一题首先用floyd来判断图的连通性,主要用来看起点到终点是否有路,还有是用来判断正环是否与终点连通;用bellman-ford来求出“最大的边”;在环的判断中关键的一句是 if(dis[y]<dis[x]+pointV[y]&&dis[x]+pointV[y]>0){if(g[y][n])return true; }   …

2014年3月25日 0条评论 0点热度 阅读全文