并不对劲的图论专题（三）：SPFA算法的优化-白红宇

并不对劲的图论专题（三）：SPFA算法的优化

阅读量：5359 次

发布时间：2019-06-15

本文共 3216 字，大约阅读时间需要 10 分钟。

1.bzoj1489->

这是个新套路。

我们希望找到最小的x，那么可以二分x，然后判断是否存在圈的边权的平均值小于等于x。

设圈的边权依次为w₁，w₂，w_3，…，w_k，平均值为p，

则有p= (w₁+w₂+w_3+…+w_k)/k ，

可以推出p*k=w₁+w₂+w_3+…+w_k，

这样就会有(w₁-p)+(w₂-p)+…+(w_k-p)=0，

当p≤x时，就会有(w₁-x)+(w₂-x)+…+(w_k-x)≤0。

这样，可以通过把所有边的边权都改为w-x，然后通过判断负环得出存在圈的边权的平均值小于等于x。

代码，不知为何常数极大：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #define maxn 3010#define maxm 10010#define eps 1e-10using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while(isdigit(ch)==0 && ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}inline void write(int x){ int f=0;char ch[20]; if(!x){puts("0");return;} if(x<0){putchar('-');x=-x;} while(x)ch[++f]=x%10+'0',x/=10; while(f)putchar(ch[f--]); putchar('\n');}int fir[maxn],nxt[maxm],v[maxm],cnt,n,m,inf[5],vis[maxn],yes;double mid,ans,L,R,dis[maxn],w[maxm];void ade(int u1,int v1,double w1){v[cnt]=v1,w[cnt]=w1,nxt[cnt]=fir[u1],fir[u1]=cnt++;}void dfs(int u){ if(yes)return; for(int k=fir[u];k!=-1;k=nxt[k]) { if(dis[v[k]]>dis[u]+(w[k]-mid)) { dis[v[k]]=dis[u]+(w[k]-mid); if(vis[v[k]]){yes=1;return;} vis[v[k]]=1,dfs(v[k]),vis[v[k]]=0; } else if(dis[v[k]]==dis[u]+(w[k]-mid)){if(vis[v[k]]){yes=1;return;}vis[v[k]]=1,dfs(v[k]),vis[v[k]]=0;} }}int check(){ yes=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)dis[j]=0.0,vis[j]=0; dfs(i); if(yes)break; } return yes;}int main(){ memset(inf,31,sizeof(inf)); memset(fir,-1,sizeof(fir)); n=read(),m=read();L=10000000.0,R=-10000000.0; for(int i=1;i<=m;i++){int x=read(),y=read();double z;scanf("%lf",&z);R=max(z,R),L=min(z,L);ade(x,y,z);}ans=R; while(fabs(R-L)>eps) { mid=(L+R)/2.0;int f=check(); //cout<
                
                 <<" "<
                 
                  <<" "<
                  
                   <

2.bzoj1715->

判负环就ok。

说个小技巧：一开始将所有点的距离设为0，而不是正无穷，这样遇到负数才会更新。

说另一个小技巧：将bfs改成dfs，在判负环时可能会更优秀，但是有可能被卡，比如上一题。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #define maxn 505#define maxm 6010using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while(isdigit(ch)==0 && ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}inline void write(int x){ int f=0;char ch[20]; if(!x){puts("0");return;} if(x<0){putchar('-');x=-x;} while(x)ch[++f]=x%10+'0',x/=10; while(f)putchar(ch[f--]); putchar('\n');}int T,n,m,ww,fir[maxn],dis[maxn],nxt[maxm],v[maxm],w[maxm],vis[maxn],cnt,yes;void ade(int u1,int v1,int w1){v[cnt]=v1,w[cnt]=w1,nxt[cnt]=fir[u1],fir[u1]=cnt++;}void reset(){memset(fir,-1,sizeof(fir)),memset(vis,0,sizeof(vis));cnt=yes=0;}void dfs(int u){ if(yes)return; for(int k=fir[u];k!=-1;k=nxt[k]) { if(dis[v[k]]>dis[u]+w[k]) { // cout<
                
                 <<" "<
                 
                  <<" "<
                  <<" "<
                   
                    <