【SPFA与Dijkstra的对比】CDOJ 1961 咸鱼睡觉觉【差分约束-负权最短路径SPFA】

差分约束系统，求最小值，跑最长路。

转自：https://www.cnblogs.com/ehanla/p/9134012.html

题解：设sum[x]为前x个咕咕中至少需要赶走的咕咕数，则 $s u m [b] - s u m [a - 1] >= c$

$s u m [b] - s u m [a - 1] >= c$

由以上式子得到边： $a - 1 点 b 点距离 c$

$i + 1 点 i 点距离 - 1$

　　　　　　　　 $i 点 i + 1 点距离 0$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 typedef long long LL;
 5 const int N=2e5+10;
 6 int n,k,cnt;
 7 bool vis[N];
 8 int head[N],d[N];
 9 struct node
10 {
11     int to,next,w;
12 }edge[N];
13 
14 void init()
15 {
16     cnt=0;
17     memset(head,-1, sizeof(head));
18 }
19 
20 void add(int u,int v,int w)
21 {
22     edge[cnt].to=v;edge[cnt].w=w,edge[cnt].next=head[u];head[u]=cnt++;
23 }
24 
25 void spfa()
26 {
27     memset(d,-INF,sizeof(d));
28     memset(vis,0,sizeof(vis));
29     queue<int> q;
30     q.push(0);
31     d[0]=0;
32     vis[0]=1;
33     while(q.size())
34     {
35         int u=q.front();q.pop();
36         vis[u]=0; // 可以重复入队，现在不在队内
37         for(int i=head[u];i!=-1;i=edge[i].next)
38         {
39             int v=edge[i].to;
40             if(d[v]<d[u]+edge[i].w) // 最长路径
41             {
42                 d[v]=d[u]+edge[i].w;
43                 if(!vis[v])
44                 {
45                     q.push(v);
46                     vis[v]=1;
47                 }
48             }
49         }
50     }
51 }
52 
53 int main()
54 {
55     init();
56     cin>>k>>n;
57     for(int i=1;i<=n;i++)
58     {
59         int a,b,c;
60         cin>>a>>b>>c;
61         // d[b]-d[a-1] >= c
62         add(a-1,b,c);
63     }
64     // 0 <= d[i+1]-d[i] <= 1
65     for(int i=0;i<k;i++)
66     {
67         add(i,i+1,0);
68         add(i+1,i,-1);  // 存在负数权值
69     }
70     spfa();
71     cout<<d[k]<<endl;
72     return 0;
73 }

求单源最短路的算法SPFA：

算法中需要的变量

1 int N;  //表示n个点，从1到n标号
2 int s,t;  //s为源点，t为终点
3 int d[N];  //d[i]表示源点s到点i的最短路
4 int pre[N];  //记录路径（或者说记录前驱）
5 queue <int> q;  //队列，
6 bool vis[N];   //vis[i]=1表示点i在队列中 vis[i]=0表示不在队列中

在整个算法中有顶点入队要记得标记vis数组，有顶点出队记得消除那个标记，顶点可以重复入队，这区别于dijkstra算法

队列+松弛操作：

读取队头顶点u，并将队头顶点u出队(消除标记)；将与点u相连的所有点v进行松弛操作，如果能更新估计值（使d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队

以此循环，直到队空为止就完成了单源最短路的求解

SPFA可以处理负权边

SPFA判断负环：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）

 1 int spfa_bfs(int s)
 2 {
 3     queue<int> q;
 4     memset(d,0x3f, sizeof(d)); // 距离矩阵
 5     memset(c,0,sizeof(c)); // 入队次数
 6     memset(vis,0, sizeof(vis));
 7     q.push(s);
 8     vis[s]=1;
 9     c[s]++;
10     int OK=1;
11     while(q.size())
12     {
13         int u=q.front();q.pop();
14         vis[u]=0;
15         for(int i=head[u];i;i=next[i])
16         {
17             int v=ver[i];
18             if(d[v]>d[u]+w[i])
19             {
20                 d[v]=d[u]+w[i];
21                 if(!vis[v])
22                 {
23                     vis[v]=1;
24                     q.push(v);
25                     c[v]++;
26                     if(c[v]>N) // 超过入队次数上限，说明有负环
27                         return OK=0;
28                 }
29             }
30         }
31     }
32     return OK;
33 }

Dijkstra的priority_queue写法与SPFA的queue写法对比:

Dijkstra+heap是用小根堆，每次取出d中未访问的最小点，来更新距离，对于这个点来说，最小距离就是当前的d。
SPFA是用双端队列，每次取出队头，来更新距离，它之后可能还会入队。是一种动态逼近法，因为每次松弛距离都会减小，所以松弛一定会有结束。如果一个点入队超过n次就存在负环。

Dijkstra

用STL中的优先队列实现堆：
while(优先队列非空)

-->队头出队，松弛它的边

-->松弛了的pair<新距离,点>入队

 1 typedef pair<int,int> P;
 2 priority_queue<P,vector<P>,greater<P> > q; // 最小堆
 3 ...
 4 while(!q.empty()){  // O(V) 加上count<n可以优化一点点 
 5     int w=q.top().first, u=q.top().second;
 6     q.pop();   // O(lgV)
 7     if(vis[u])continue; vis[u]=true;
 8     //++count;
 9     for(int i=head[u];i;i=edge[i].next){ // Sum -> O(E)
10         int v=edge[i].to;
11         if(d[v]>d[u]+edge[i].w){
12             d[v]=d[u]+edge[i].w;
13             q.push(P(d[v],v));  // O(lgV)
14         }
15     }
16 }

SPFA：

while(队非空)

-->队头出队，取消标记，松弛它的边

-->松弛了且不在队内的点入队，并标记

 1 while(!q.empty()){
 2     int u=q.front(); q.pop();
 3     vis[u]=false;
 4     for(int i=head[u];i;i=edge[i].next){
 5         int v=edge[i].to;
 6         if(d[v]>d[u]+edge[i].w){
 7             d[v]=d[u]+edge[i].w;
 8             if(!vis[v])vis[v]=true,q.push(v);
 9         }
10     }
11 }

Dijkstra和Prim也很相似，它们的区别主要是d的含义，前者是到s的临时最短距离[s->每一点]，后者是到树的临时最短距离[边长]，相同点是，每次找最小的d更新其它点的距离。

秒客网

【SPFA与Dijkstra的对比】CDOJ 1961 咸鱼睡觉觉【差分约束-负权最短路径SPFA】

相关文章