bool bf() {

    memset(dis,INF,sizeof(dis));

    dis[1]=0;

    for(int j=1; j<=n-1; j++) {

    for(int i=1; i<=m; i++) {

        dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i]);

        if(w[i]>=0)

            dis[u[i]]=min(dis[u[i]],dis[v[i]]+w[i]);//双向边

            }

    }
    //多一次松弛
    for(int i=1; i<=m; i++) {

        if(dis[u[i]]!=INF&&dis[v[i]]>dis[u[i]]+w[i])return 1;

        if(w[i]>=0) {

            if(dis[v[i]]!=0x7f&&dis[u[i]]>dis[v[i]]+w[i])return 1;//双向边

            }

    }

    return 0;

}

2020.8.26 UPDATE

vector<pair<int,int> >G[50003];
struct SPFA_WITH_NEG_CIRC {
    const static int MAXN = 50000;
    int dis[MAXN+5],dpt[MAXN+5];
    bool vis[MAXN+5];
    bool spfa(int S,bool cir=0) {
        for(int i=0; i<=n; i++)dis[i]=0x7ffffff,vis[i]=dpt[i]=0;
        dis[S]=0;
        deque<int>q;
        q.push_back(S);
        while(!q.empty()) {
            int x=q.front();
            q.pop_front();
            vis[x]=0;
            int sz=G[x].size();
            for(int i=0; i<sz; i++) {
                int y=G[x][i].first,w=G[x][i].second;
                if(dis[y]>dis[x]+w) {
                    dis[y]=dis[x]+w;
                    if(!vis[y]) {
                        vis[y]=1;
                        if(cir&&++dpt[y]>=n)return 1;
                        if(cir)q.push_back(y);
                    }
                }
            }
        }
        return 0;
    }
} T;

Categories:

Tags:

No responses yet

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

近期评论
归档
分类