spfa的SLF 和 LLL优化算法

   一. spfa的SLF优化，就是双向队列优化，在spfa压入队列时，判断要压入队首还是队尾。这个优化可以优化15%~20%。

   二. spfa的LLL优化，就是记录现在队列中元素所代表值的平均值，和要压入元素的值相比较，如果大于平均值，直接压入对列尾部，LLL优化+SLF优化可以优化大概50%。

  我们以一道判负环的题为例子，来讲解一下。

Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Output

Sample Input

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

Sample Output

NO
YES

Hint

Source

#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
struct s1{int to;int val;int next;
}a[10000];
int head[10000];
int dis[10000];
int book[10000];
int cnt;
void add(int u,int v,int w)
{a[++cnt].to=v;a[cnt].val=w;a[cnt].next=head[u];head[u]=cnt;
}
int main()
{int F;scanf("%d",&F);while(F--){int n,m,w;cnt=0;scanf("%d%d%d",&n,&m,&w);memset(book,0,sizeof(book));memset(head,-1,sizeof(head));memset(a,0,sizeof(a));for(int i=0;iq;memset(dis,inf,sizeof(dis));dis[1]=0;book[1]=1;q.push(1);int cn[10000];int flag=0;memset(cn,0,sizeof(cn));cn[1]=1;while(!q.empty()){int p=q.front();q.pop();book[p]=0;for(int i=head[p];i!=-1;i=a[i].next){if(dis[a[i].to]>dis[p]+a[i].val){dis[a[i].to]=dis[p]+a[i].val;if(book[a[i].to]==0){book[a[i].to]=1;cn[a[i].to]++;if(cn[a[i].to]>=n){flag=1;break;}q.push(a[i].to);}}}if(flag==1)break;}if(flag==1)printf("YES\n");elseprintf("NO\n");}
}

#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
struct s1{int to;int val;int next;
}a[10000];
int head[10000];
int dis[10000];
int book[10000];
int cnt;
void add(int u,int v,int w)
{a[++cnt].to=v;a[cnt].val=w;a[cnt].next=head[u];head[u]=cnt;
}
int main()
{int F;scanf("%d",&F);while(F--){int n,m,w;cnt=0;scanf("%d%d%d",&n,&m,&w);memset(book,0,sizeof(book));memset(head,-1,sizeof(head));memset(a,0,sizeof(a));for(int i=0;iq;memset(dis,inf,sizeof(dis));dis[1]=0;book[1]=1;q.push_back(1);int cn[10000];int flag=0;memset(cn,0,sizeof(cn));cn[1]=1;while(!q.empty()){int p=q.front();q.pop_front();book[p]=0;for(int i=head[p];i!=-1;i=a[i].next){if(dis[a[i].to]>dis[p]+a[i].val){dis[a[i].to]=dis[p]+a[i].val;if(book[a[i].to]==0){book[a[i].to]=1;cn[a[i].to]++;if(cn[a[i].to]>=n){flag=1;break;}if(!q.empty()&&dis[a[i].to]

#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
struct s1{int to;int val;int next;
}a[10000];
int head[10000];
int dis[10000];
int book[10000];
int cnt;
void add(int u,int v,int w)
{a[++cnt].to=v;a[cnt].val=w;a[cnt].next=head[u];head[u]=cnt;
}
int main()
{int F;scanf("%d",&F);while(F--){int n,m,w;cnt=0;scanf("%d%d%d",&n,&m,&w);memset(book,0,sizeof(book));memset(head,-1,sizeof(head));memset(a,0,sizeof(a));for(int i=0;iq;memset(dis,inf,sizeof(dis));dis[1]=0;book[1]=1;q.push_back(1);int cn[10000];int flag=0;memset(cn,0,sizeof(cn));cn[1]=1;long long sum=0;int len=1;while(!q.empty()){int p=q.front();q.pop_front();if(dis[p]*len>sum)  //LLL优化{q.push_back(p);continue;}sum-=dis[p];book[p]=0;len--;for(int i=head[p];i!=-1;i=a[i].next){if(dis[a[i].to]>dis[p]+a[i].val){dis[a[i].to]=dis[p]+a[i].val;if(book[a[i].to]==0){book[a[i].to]=1;cn[a[i].to]++;if(cn[a[i].to]>=n){flag=1;break;}if(!q.empty()&&dis[a[i].to]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！