ShortestPath:Wormholes(POJ 3259)

时间:2023-03-09 09:56:07
ShortestPath:Wormholes(POJ 3259)

              ShortestPath:Wormholes(POJ 3259)

              田里的虫洞

  题目大意:就是这个农夫的田里有一些虫洞,田有很多个点,点与点之间会存在路,走过路需要时间,并且这些点存在虫洞,可以使农夫的时间退回到时间之前,问你农夫是否真的能回到时间之前?

  读完题:这一题就是很明显了,就是要你找负值圈嘛!立马上Bellman_Ford算法

  

#include <iostream>
#include <functional>
#include <algorithm>
#include <queue>
#define MAX_N 501 using namespace std; typedef struct edge_
{
int cost;
int from;
int to;
}Edge;
static Edge Gragh_Edge[MAX_N *MAX_N];
static int dp_edge[MAX_N*MAX_N * + ]; bool Search_Bellman_Ford(const int,const int,const int); int main(void)
{
int Farm_sum, Path_sum, Node_sum, holes_sum, start, end, times;
while (~scanf("%d", &Farm_sum))
{
for (int i = ; i < Farm_sum; i++)
{
scanf("%d%d%d", &Node_sum, &Path_sum, &holes_sum);
for (int j = ; j < * Path_sum; j += )
{
scanf("%d%d%d", &start, &end, &times);
//双向边
Gragh_Edge[j].from = start; Gragh_Edge[j].to = end; Gragh_Edge[j].cost = times;
Gragh_Edge[j + ].from = end; Gragh_Edge[j + ].to = start; Gragh_Edge[j + ].cost = times;
}
for (int j = * Path_sum; j < holes_sum + * Path_sum; j++)
{
scanf("%d%d%d", &start, &end, &times);
Gragh_Edge[j].from = start; Gragh_Edge[j].to = end; Gragh_Edge[j].cost = -times;//单向边,负值,只要覆盖掉之前的正值就可以了
}
if (Search_Bellman_Ford(Node_sum, Path_sum,holes_sum))
printf("YES\n");
else printf("NO\n");
}
}
return ;
} bool Search_Bellman_Ford(const int Node_sum, const int Path_sum, const int holes_sum)
{
int paths = Path_sum * + holes_sum;
memset(dp_edge, , sizeof(dp_edge)); for (int i = ; i < Node_sum; i++)
for (int j = ; j < paths; j++)
{
Edge e = Gragh_Edge[j];
if (dp_edge[e.from] + e.cost < dp_edge[e.to])
{
dp_edge[e.to] = dp_edge[e.from] + e.cost;
if (i == Node_sum - ) return true;
}
}
return false;
}

ShortestPath:Wormholes(POJ 3259)

  结果很高兴地1A了

  当然,这个时间有点慢,我们可以使用SPFA算法优化他

  不过在这之前我们有必要搞清楚什么是SPFA算法,其实这个算法是Bellman_Ford的优化,BF这个算法的缺点在于他一定要把所有的点都扫描n-1次才能确定是否有负值圈,这就造成了低效,而我们知道,其实我们没有必要等所有的节点都到i=n-1的层面,因为如果图不存在负值圈,那么Bellman_Ford以及Dijkstra算法肯定不会经过一个顶点两次,如果存在负圈,那么肯定至少存在一个节点,经过n次以上,那么我们完全可以利用这个性质,在扫n-1次前就找到这个节点,而SPFA算法就是利用这个原理。

  SPFA算法有点像BFS算法,他是充分利用点的关系来找最短路的,而且这个算法还支持负值圈(当然这个算法找正值的最短路径不及Dijkstra那么快),复杂度是O(EV)(没有负值圈的时候),他像BFS一样,不断地把邻接节点入队,然后出队,利用一个used域,我们就可以找到那些不在队中的节点,如果不存在负值圈,那么这些节点就不会经过两次,最终这个算法会以队列为空结束,如果存在负值圈,那么我们需要其他判断方法,这个方法就是判断一个节点是否被进入V次以上(之前说过的性质)。

  其他的也像BF算法一样,还是维护一个dp数组来确定是否更新就可以了

  SPFA因为要对邻接点做处理,所以如果能存边,那就最好了,所以推荐用邻接表,另外ACM因为还是以速度为主,大量的申请内存会导致效率下降,所以如果要维护邻接表,最好还是用向前边的方法维护,就是维护一个head数组,head数组指向第一条边,接下来边指向其他的边就可以了!

  另外这一题因为我们不知道是不是联通,用SPFA还是要稍微判断一下节点有没有经过的问题,没有经过我们就重新设立start节点(这一题讨论版很多人都没考虑到这一点,那是运气好,这一题是联通的,so)

  

 #include <iostream>
#include <functional>
#include <algorithm>
#define MAX_N 501 using namespace std; typedef struct edge_
{
int cost;
int next;
int to;
}Edge;
typedef int Queue, Position;
static Edge Gragh_Edge[MAX_N *MAX_N + ];
static Position head[MAX_N];//用邻接表去存图,这个是节点头
static bool used[MAX_N];//SPFA算法要用到的标记域
static bool known[MAX_N];//判断图是否联通的关键
static int out[MAX_N];//看点出列了多少次
static int dp_edge[MAX_N];//dp数组记录到该点的最短距离
Queue que[MAX_N *MAX_N];//队列 bool Search_Spfa(const int, const int, const int);
void Renew(void); int main(void)
{
int Farm_sum, Path_sum, Node_sum, holes_sum, start, end, times;
while (~scanf("%d", &Farm_sum))
{
for (int i = ; i < Farm_sum; i++)
{
memset(head, -, sizeof(head));
memset(used, , sizeof(used));
memset(known, , sizeof(known));
memset(out, , sizeof(out));
memset(dp_edge, , sizeof(dp_edge));
scanf("%d%d%d", &Node_sum, &Path_sum, &holes_sum);
for (int j = ; j < * Path_sum; j += )
{
scanf("%d%d%d", &start, &end, &times);
//双向边
Gragh_Edge[j].next = head[start]; Gragh_Edge[j].to = end; Gragh_Edge[j].cost = times;
head[start] = j;
Gragh_Edge[j + ].next = head[end]; Gragh_Edge[j + ].to = start; Gragh_Edge[j + ].cost = times;
head[end] = j + ;
}
for (int j = * Path_sum; j < holes_sum + * Path_sum; j++)
{
scanf("%d%d%d", &start, &end, &times);
Gragh_Edge[j].next = head[start]; Gragh_Edge[j].to = end; Gragh_Edge[j].cost = -times;//单向边,负值,只要覆盖掉之前的正值就可以了
head[start] = j;
}
if (Search_Spfa(Node_sum, Path_sum, holes_sum))
printf("YES\n");
else printf("NO\n");
}
}
return ;
} bool Search_Spfa(const int Node_sum, const int Path_sum, const int holes_sum)
{
Position top, bot, out_node; for (int i = ; i <= Node_sum; i++)
{
if (known[i]) continue;
top = bot = ;
known[i] = ; que[bot++] = i; while (top != bot)
{
out_node = que[top++];
known[out_node] = ;
used[out_node] = ;//出队了就标记为0
out[out_node]++;
if (out[out_node] > Node_sum) return true; for (int k = head[out_node]; k != -; k = Gragh_Edge[k].next)//此点的邻接边全部找出来
{
if (dp_edge[Gragh_Edge[k].to] > dp_edge[out_node] + Gragh_Edge[k].cost)
{
dp_edge[Gragh_Edge[k].to] = dp_edge[out_node] + Gragh_Edge[k].cost;
if (!used[Gragh_Edge[k].to])//to不在队列内
{
used[Gragh_Edge[k].to] = ;
que[bot++] = Gragh_Edge[k].to;
}
}
}
}
}
return false;
}

ShortestPath:Wormholes(POJ 3259)

  速度快了一倍