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

时间:2021-05-20 20:34:25

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

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

题解:设sum[x]为前x个咕咕中至少需要赶走的咕咕数,则sum[b]sum[a1]>=c表示[a,b]区间至少赶走c只。题目中选择的是最少,我们需要跑最长路,因存在负边,所以以SPFA进行操作。

d[v]>=d[u]+w,前面我们可以推出第一个式子sum[b]>=sum[a1]+c,但是如果只连这些边,整张图连通不起来。我们发现ii+1存在关系0<=sum[i+1]sum[i]<=1,这个其实就是表示i+1那个位置赶与不赶。

推出第二个和第三个式子:sum[i]>=sum[i+1]1sum[i+1]>=sum[i]+0

由以上式子得到边:a1 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 }

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