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 * 2 + 200];

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 = 0; i < Farm_sum; i++)
        {
            scanf("%d%d%d", &Node_sum, &Path_sum, &holes_sum);
            for (int j = 0; j <2 * Path_sum; j += 2)
            {
                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 + 1].from = end; Gragh_Edge[j + 1].to = start; Gragh_Edge[j + 1].cost = times;
            }
            for (int j = 2 * Path_sum; j < holes_sum + 2 * 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
");
            else printf("NO
");
        }
    }
    return 0;
}

bool Search_Bellman_Ford(const int Node_sum, const int Path_sum, const int holes_sum)
{
    int paths = Path_sum * 2 + holes_sum;
    memset(dp_edge, 0, sizeof(dp_edge));

    for (int i = 0; i < Node_sum; i++)
        for (int j = 0; 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 - 1) return true;
            }
        }
    return false;
}

　　结果很高兴地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）

　　

 1 #include <iostream>
 2 #include <functional>
 3 #include <algorithm>
 4 #define MAX_N 501
 5 
 6 using namespace std;
 7 
 8 typedef struct edge_
 9 {
10     int cost;
11     int next;
12     int to;
13 }Edge;
14 typedef int Queue, Position;
15 static Edge Gragh_Edge[MAX_N *MAX_N + 200];
16 static Position head[MAX_N];//用邻接表去存图,这个是节点头
17 static bool used[MAX_N];//SPFA算法要用到的标记域
18 static bool known[MAX_N];//判断图是否联通的关键
19 static int out[MAX_N];//看点出列了多少次
20 static int dp_edge[MAX_N];//dp数组记录到该点的最短距离
21 Queue que[MAX_N *MAX_N];//队列
22 
23 bool Search_Spfa(const int, const int, const int);
24 void Renew(void);
25 
26 int main(void)
27 {
28     int Farm_sum, Path_sum, Node_sum, holes_sum, start, end, times;
29     while (~scanf("%d", &Farm_sum))
30     {
31         for (int i = 0; i < Farm_sum; i++)
32         {
33             memset(head, -1, sizeof(head));
34             memset(used, 0, sizeof(used));
35             memset(known, 0, sizeof(known));
36             memset(out, 0, sizeof(out));
37             memset(dp_edge, 0, sizeof(dp_edge));
38             scanf("%d%d%d", &Node_sum, &Path_sum, &holes_sum);
39             for (int j = 0; j <2 * Path_sum; j += 2)
40             {
41                 scanf("%d%d%d", &start, &end, &times);
42                 //双向边
43                 Gragh_Edge[j].next = head[start]; Gragh_Edge[j].to = end; Gragh_Edge[j].cost = times;
44                 head[start] = j;
45                 Gragh_Edge[j + 1].next = head[end]; Gragh_Edge[j + 1].to = start; Gragh_Edge[j + 1].cost = times;
46                 head[end] = j + 1;
47             }
48             for (int j = 2 * Path_sum; j < holes_sum + 2 * Path_sum; j++)
49             {
50                 scanf("%d%d%d", &start, &end, &times);
51                 Gragh_Edge[j].next = head[start]; Gragh_Edge[j].to = end; Gragh_Edge[j].cost = -times;//单向边，负值，只要覆盖掉之前的正值就可以了
52                 head[start] = j;
53             }
54             if (Search_Spfa(Node_sum, Path_sum, holes_sum))
55                 printf("YES
");
56             else printf("NO
");
57         }
58     }
59     return 0;
60 }
61 
62 bool Search_Spfa(const int Node_sum, const int Path_sum, const int holes_sum)
63 {
64     Position top, bot, out_node;
65 
66     for (int i = 1; i <= Node_sum; i++)
67     {
68         if (known[i]) continue;
69         top = bot = 0;
70         known[i] = 1; que[bot++] = i;
71 
72         while (top != bot)
73         {
74             out_node = que[top++];
75             known[out_node] = 1;
76             used[out_node] = 0;//出队了就标记为0
77             out[out_node]++;
78             if (out[out_node] > Node_sum) return true;
79 
80             for (int k = head[out_node]; k != -1; k = Gragh_Edge[k].next)//此点的邻接边全部找出来
81             {
82                 if (dp_edge[Gragh_Edge[k].to] > dp_edge[out_node] + Gragh_Edge[k].cost)
83                 {
84                     dp_edge[Gragh_Edge[k].to] = dp_edge[out_node] + Gragh_Edge[k].cost;
85                     if (!used[Gragh_Edge[k].to])//to不在队列内
86                     {
87                         used[Gragh_Edge[k].to] = 1;
88                         que[bot++] = Gragh_Edge[k].to;
89                     }
90                 }
91             }
92         }
93     }
94     return false;
95 }

　　速度快了一倍

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Philip-Tell-Truth/p/4908555.html