kkogoro

判断环
判断环判负环如果存在负环,则存在点满足源点到它的最短路上有超过 $n-1$ 条边Bellman-Ford方法利用 ...
扫描右侧二维码阅读全文
08
2018/11

判断环

判断环

判负环

如果存在负环,则存在点满足源点到它的最短路上有超过 $n-1$ 条边

Bellman-Ford方法

利用 $Bellman-Ford$ 跑最短路,如果进行了 $n$ 轮外层循环仍然可以松弛,就存在负环,如果 $n-1$ 轮以内外层循环就不可松弛则没有负环。

SPFA方法一

利用 $SPFA$ 算法跑最短路,如果一个点入队次数大于等于 $n$ 次,则证明存在负环。

SPFA方法二

利用 $SPFA$ 算法跑最短路, $cnt_{x}$ 表示从源点到 $x$ 的最短路径包含的边数, $cnt_{s}=0$ ,如果可以松弛 $dis[v]=dis[u]+w$ ,则 $cnt[v]=cnt[u]+1$ 。如果发现 $cnt[x]\geq n$ ,则存在负环。

需要注意的地方

  1. 如果图可能不连通,需要加入超级源点。
  2. 如果你加入了超级源点(显式),算法中的 $n'$ 就是 $n+1$ 。
  3. 如果不清楚边界如何取,可以稍稍增大边界限制,但是可能会导致超时(需要绕环跑)。
  4. 可以通过构造的数据来检验自己的 $n$ 是否设了。

代码

使用了 洛谷P3385 ,并且使用超级源点,第9个数据点有问题,SPFA方法一使用超级源点会WA(截至2018.10.30)

Bellman-Ford方法
#include <iostream>
#include <cstring>
#include <cstdio>


const int MAXN = 2007;
const int MAXM = 3007;


int to[MAXM << 1], nextEdge[MAXM << 1], head[MAXN], cntEdge, val[MAXM << 1];
inline void insert(int u, int v, int w) {
    ++cntEdge;
    to[cntEdge] = v, val[cntEdge] = w, nextEdge[cntEdge] = head[u], head[u] = cntEdge;
    return;    
}


int dis[MAXN];
inline bool BF(int n) {
    for (int i = 1; i <= n; ++i) {
        dis[i] = 0;
    }
    for (int i = 1; i <= n + 1; ++i) {
        bool flag = false;
        for (int u = 1; u <= n; ++u) {
            for (int it = head[u]; it != 0; it = nextEdge[it]) {
                int v = to[it];
                if (dis[v] > dis[u] + val[it]) {
                    dis[v] = dis[u] + val[it];
                    flag = true;
                }
            }
        }
        if (flag == false) break;
        if (flag == true && i == n + 1) return true;
    }
    return false;
}


int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        cntEdge = 0;
        memset(head, 0, sizeof head);
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            insert(u, v, w);
            if (w >= 0) insert(v, u, w);
        }
        if (BF(n) == true) {
            printf("YE5\n");
        }
        else {
            printf("N0\n");
        }
    }
    return 0;
}
SPFA方法一
#include <iostream>
#include <cstring>
#include <cstdio>


const int MAXN = 2007;
const int MAXM = 3007;


int to[MAXM << 1], nextEdge[MAXM << 1], head[MAXN], cntEdge, val[MAXM << 1];
inline void insert(int u, int v, int w) {
    ++cntEdge;
    to[cntEdge] = v, val[cntEdge] = w, nextEdge[cntEdge] = head[u], head[u] = cntEdge;
    return;    
}



struct Queue {
    static const int maxn = 1 << 11;
    static const int mod = maxn - 1;
    int data[maxn], head, tail;
    inline void init() {
        head = 1, tail = 0;
        return;
    }
    inline void push(int x) {
        data[++tail & mod] = x;
        return;
    }
    inline void pop() {
        ++head;
        return;
    }
    inline int front() {
        return data[head & mod];
    }
    inline bool empty() {
        return head > tail;
    }
} q;


int cnt[MAXN], dis[MAXN];
bool inq[MAXN];
inline bool SPFA(int n) {
    q.init();
    for (int i = 1; i <= n; ++i) {
        cnt[i] = 1;
        dis[i] = 0;
        inq[i] = true;
        q.push(i);
    }
    while (q.empty() == false) {
        int u = q.front();
        inq[u] = false;
        q.pop();
        for (int it = head[u]; it != 0; it = nextEdge[it]) {
            int v = to[it];
            if (dis[v] > dis[u] + val[it]) {
                dis[v] = dis[u] + val[it];
                ++cnt[v];
                if (cnt[v] >= n + 1) return true;
                if (inq[v] == false) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    
    return false;
}


int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        cntEdge = 0;
        memset(head, 0, sizeof head);
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            insert(u, v, w);
            if (w >= 0) insert(v, u, w);
        }
        if (SPFA(n) == true) {
            printf("YE5\n");
        }
        else {
            printf("N0\n");
        }
    }
    return 0;
}
SPFA方法二
#include <iostream>
#include <cstring>
#include <cstdio>


const int MAXN = 2007;
const int MAXM = 3007;


int to[MAXM << 1], nextEdge[MAXM << 1], head[MAXN], cntEdge, val[MAXM << 1];
inline void insert(int u, int v, int w) {
    ++cntEdge;
    to[cntEdge] = v, val[cntEdge] = w, nextEdge[cntEdge] = head[u], head[u] = cntEdge;
    return;    
}


struct Queue {
    static const int maxn = 1 << 11;
    static const int mod = maxn - 1;
    int data[maxn], head, tail;
    inline void init() {
        head = 1, tail = 0;
        return;
    }
    inline void push(int x) {
        data[++tail & mod] = x;
        return;
    }
    inline void pop() {
        ++head;
    }
    inline int front() {
        return data[head & mod];
    }
    inline bool empty() {
        return head > tail;
    }
} q;


int cnt[MAXN], dis[MAXN];
bool inq[MAXN];
inline bool SPFA(int n) {
    q.init();
    for (int i = 1; i <= n; ++i) {
        cnt[i] = 1;
        dis[i] = 0;
        inq[i] = true;
        q.push(i);    
    }
    
    while (q.empty() == false) {
        int u = q.front();
        inq[u] = false;
        q.pop();
        for (int it = head[u]; it != 0; it = nextEdge[it]) {
            int v = to[it];
            if (dis[v] > dis[u] + val[it]) {
                dis[v] = dis[u] + val[it];
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n + 1) return true;
                if (inq[v] == false) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    
    return false;
}


int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        cntEdge = 0;
        memset(head, 0, sizeof head);
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            insert(u, v, w);
            if (w >= 0) insert(v, u, w);
        }
        if (SPFA(n) == true) {
            printf("YE5\n");
        }
        else {
            printf("N0\n");
        }
    }
    return 0;
}

判正环

修改边权方法

边权取反,判负环

修改算法方法

$SPFA$ 松弛条件改为 $dis_{v} < dis_{u} + w$

Last modification:November 8th, 2018 at 05:20 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment