spfa优化 SLF LLL

2013.10.23 更新

之前写的时候不知道在想什么，整理模板时才发现写挫了，现在重发一个

SPFA 是按照 FIFO 的原则更新距离的, 没有考虑到距离标号的作用. 实现中 SPFA 有两个非常著名的优化: SLF 和 LLL.

　　SLF: Small Label First 策略.
　　实现方法是, 设队首元素为 , 队列中要加入节点 , 在 时加到队首而不是队尾, 否则和普通的 SPFA 一样加到队尾. 这可以用个优先级队列维护

　　LLL: Large Label Last 策略. 
　　实现方法是, 设队列 中的队首元素为 , 距离标号的平均值为 , 每次出队时, 若 , 把 移到队列末尾, 如此反复, 直到找到一个 使 , 将其出队.

/**复杂度分析：普通SPFA km kmax=n 不适合稠密图 一般为2优先级队列  加入节点复杂度logn 节点数太多时适得其反，对于特殊数据速度略小于普通spfa对于随机图效果很好手动模拟SLF，LLL 复杂度低于优先级队列，最坏情况与普通SPFA持平*/#define Maxn 100010//最大点数
#define Maxm 400010//最大边数，无向图要建双向边
int w[Maxm],u[Maxm],next[Maxm],cnt;
int first[Maxn],havein[Maxn];//havin为入队次数
long long d[Maxn];//距离
int n;
bool in[Maxn];//队中标志
inline void add(int vn,int un,int wn){//邻接表存储u[cnt]=un;w[cnt]=wn;next[cnt]=first[vn];first[vn]=cnt++;
}
struct node{int v,dd;node(int &a):v(a),dd(d[a]){};bool operator< (const node& a)const{return dd>a.dd;}
};
priority_queue<node> q; //利用优先级队列SLF和LLL
bool spfa(int s){int i,now,ne,t;memset(in,0,sizeof(in));memset(havein,0,sizeof(havein));for(i=0;i<n;i++)d[i]=INF; //memset(d,0x3f,sizeof(d));d[s]=0;in[s]=1;q.push(s);while(!q.empty()){now=q.top().v;q.pop();if(!in[now])continue;in[now]=0;for(i=first[now];~i;i=next[i]){ne=u[i];if(d[ne]<=(t=d[now]+w[i]))continue;d[ne]=t; in[ne]=1; q.push(ne);if(++havein[ne]>n)return 0;//判断有无负环}}return 1;//返回1为正常，0为有负环
}
#define M 200000  //手动模拟
int q[M];
bool spfa(int s){int i,now,ne,t;memset(in,0,sizeof(in));memset(havein,0,sizeof(havein));memset(d,0x3f,sizeof(d));int l,r,len;l=r=len=0;long long sum=0;d[s]=0;in[s]=havein[s]=1;q[r++]=s;len++;while(l!=r){now=q[l++];if(l==M)l=0;if(d[now]*len>sum){//LLLq[r++]=now;if(r==M)r=0;continue;}len--; sum-=d[now]; in[now]=0;for(i=first[now];~i;i=Next[i]){ne=u[i];if(d[ne]<=(t=d[now]+w[i]))continue;d[ne]=t;if(in[ne])continue;in[ne]=1;if(t<=d[q[l]]){ //SLFif(--l<0)l=M-1;q[l]=ne;}else{q[r++]=ne;if(r==M)r=0;}len++; sum+=t;if(++havein[ne]>n)return 0;}}return 1;//返回1为正常，0为有负环
}
void init()//边初始化
{cnt=0;memset(first,-1,sizeof(first));
}