c++ dfs_spfa版本(性能超过队列式spfa, 74ms vs 186ms)

不需要进行经验常数判断, 不会损失算法的正确性换取性能提升

#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;

const int N=680;
const int M=100005;
const double EPS=1e-4;

int n;
int head[N], E=0; // head[N]存储头结点, E存储边的数量
double dist[N];
bool inStack[N], flag;

struct Edge{
    int v, ne;
    double w;
}e[M];

inline void init(){
    memset(head, -1, sizeof head);
    E=0;
}

inline void add(int u, int v, double w){
    e[E].v=v;
    e[E].w=w;
    e[E].ne=head[u];
    head[u]=E++;
}

bool spfa_dfs(int u, double k){
    inStack[u]=true; // 当前节点u在栈中
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(dist[v]<dist[u]+e[i].w-k){
            dist[v]=dist[u]+e[i].w-k;
            if(inStack[v]) return true;
            if(spfa_dfs(v, k)) return true;
        }
    }
    inStack[u]=false;
    return false;
}

bool f(double k){
    memset(dist, 0x00, sizeof dist);
    memset(inStack, 0x00, sizeof inStack);
    for(int i=0; i<N; ++i){
        if(~head[i] && spfa_dfs(i, k)) return true;
    }
    return false;
}

inline int code(char ca, char cb){return (ca-'a')*26+(cb-'a');}

void bs(){
    double l=0, r=1005;
    bool ans=false;
    while(l+EPS<r){
        double mid=l+(r-l)/2;
        if(f(mid)){
            ans=true;
            l=mid;
        }
        else r=mid;
    }
    if(!ans) printf("No solution\n");
    else printf("%.2f\n", l);
}

int main(){
    char str[1005];
    while(scanf("%d", &n), n){
        init();
        for(int i=0; i<n; ++i){
            scanf("%s", str);
            int len=strlen(str);
            int u=code(str[0], str[1]);
            int v=code(str[len-2], str[len-1]);
            add(u, v, (double)len);
        }
        bs(); // 进行二分搜索
    }
    return 0;
}