当前位置：首页 > article >正文

图论——spfa判负环

article 2025/3/7 4:59:08

负环

图 $G$ 中存在一个回路，该回路边权之和为负数，称之为负环。

spfa求负环

方法1:统计每个点入队次数, 如果某个点入队n次, 说明存在负环。
证明：一个点入队n次，即被更新了n次。一个点每次被更新时所对应最短路的边数一定是递增的，也正因此该点被更新n次那么该点对应的的最短路长度一定大于等于n，即路径上点的个数至少为n+1。根据抽屉原理，路径中至少有一个顶点出现两次, 也就是路径中存在环路。而算法保证只有距离减少才会更新, 所以环路权值之和为负数。

方法2:统计从起点到任意顶点最短路经过的边数, 若某点对应边数 $c n t \geq n$ , 则也说明负环。
方法2根据抽屉原理易证。
我们一般采用方法2才求负环。

acwing904.虫洞

spfa求负环模板题

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 5210;
int h[N], w[M], e[M], ne[M], tot;
int dist[N];
int cnt[N];
bool st[N];
int q[N];
int t;
int n, m, k;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
bool spfa()
{
    memset(dist, 0, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        st[i] = 1;
        q[tt ++ ] = i;
    }
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] == n) return true;
                if (st[j]) continue;
                st[j] = 1;
                q[tt ++ ] = j;
                if (tt == N) tt = 0;
            }
        }
    }
    return false;
}
int main()
{
    cin >> t;
    while (t -- )
    {
        cin >> n >> m >> k;
        tot = 0;
        memset(h, -1, sizeof h);
        while (m -- )
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c), add(b, a, c);
        }
        while (k -- )
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, -c);
        }
        bool t = spfa();
        if (t) puts("YES");
        else puts("NO");
    }
    return 0;
}

本题要求我们求出环中存在的 $\frac{\sum f[i]}{\sum t[i]}$ 的最大值，如果直接对问题进行求解是有难度的，考虑二分答案。首先易知，答案的范围在 $[1/1000, 1000]$ 之间，假设我们当前二分到的答案为 $mi d$ ,如果 $an s < mi d$ ,我们可以去左半区间进行寻找,反之我们去右半区间寻找。
$\frac{\sum f[i]}{\sum t[i]}> mid$
$\sum f[i]> mid*\sum t[i]$
$\sum f[i]-mid*\sum t[i]> 0$
$\sum (f[i]-mid*t[i])> 0$
$\sum (mid*t[i]-f[i])< 0$
经过转换后，问题就等价于把图中边权换为 $mi d * t [i] - f [i]$ ,然后判断图中是否存在负环，存在负环则说明图中存在 $\frac{\sum f[i]}{\sum t[i]}>mid$ 的环。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 5010;
int h[N], e[M], ne[M], tot;
int wf[N], wt[M];
int q[N];
double dist[N];
int cnt[N];
bool st[N];
int n, m;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], wt[tot] = c, h[a] = tot ++ ;
}
bool check(double x)
{
    memset(dist, 0, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        st[i] = 1;
        q[tt ++ ] = i;
    }
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            double w = x * wt[i] - wf[t];
            if (dist[j] > dist[t] + w)
            {
                dist[j] = dist[t] + w;
                cnt[j] = cnt[t] + 1;
                if (cnt[j] == n) return true;
                if (st[j]) continue;
                st[j] = 1;
                q[tt ++ ] = j;
                if (tt == N) tt = 0;
            }

        }
    }
    return false;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        cin >> wf[i];
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    double l = 0, r = 1001;
    while (r - l > 1e-4)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2lf", l);
    return 0;
}

acwing1165.单词环

我们第一感觉是把每一个单词看作一个节点，这样一来节点总数 $n=10^5$ ，最坏情况是所有单词都可以互相进行匹配，这样一来边数 $m=10^5*10^5=10^{10}$ ，考虑其他建图方式。
我们可以把每个单词看作一条边，这样一来边数 $m=10^5$ ,每个单词开头结尾两个字母为节点，节点总数 $n = 26 * 26 = 676$ 。
本题要求我们求所有环的 $\frac{\sum w[i]}{\sum 1}$ 最大值。和上题相同，二分答案，答案区间为 $[1/1000, 1000]$ 。
$\frac{\sum w[i]}{\sum 1}> mid$
$\sum w[i]> mid$
$\sum w[i]-mid> 0$
$\sum (w[i]-mid)> 0$
$\sum (mid-w[i])< 0$
经过转换后，问题就等价于把图中边权换为 $mi d - w [i]$ ,然后判断图中是否存在负环，存在负环则说明图中存在 $\frac{\sum w[i]}{\sum 1}>mid$ 的环。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 26 * 26 + 10, M = 100010;
int h[N], e[M], ne[M], w[M], tot;
double dist[N];
bool st[N];
int cnt[N];
int q[N];
char s[1010];
int n;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
bool check(double mid)
{
    memset(st, 0, sizeof st);
    memset(dist, 0, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    int hh = 0, tt = 0;
    for (int i = 0; i < 26 * 26; i ++ )
    {
        q[tt ++ ] = i;
        st[i] = 1;
    }
    int count = 0;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        st[t] = 0;
        if (hh == N) hh = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            double ww = mid - w[i];
            if (dist[j] > dist[t] + ww)
            {
                dist[j] = dist[t] + ww;
                cnt[j] = cnt[t] + 1;
                if (++ count == 10000) return true;
                if (cnt[j] == N) return true;
                if (st[j]) continue;
                st[j] = 1;
                q[tt ++ ] = j;
                if (tt == N) tt = 0;
            }
        }
    }
    return false;
}
int main()
{
    while (cin >> n, n)
    {
        memset(h, -1, sizeof h);
        tot = 0;
        for (int i = 1; i <= n; i ++ )
        {
            cin >> s;
            int len = strlen(s);
            if (len < 2) continue;
            int ll = (s[0] - 'a') * 26 + s[1] - 'a';
            int rr = (s[len - 2] - 'a') * 26 +s[len - 1] - 'a';
            add(ll, rr, len);
        }
        double l = 0, r = 1001;
        if (!check(0)) puts("No solution");
        else{
            while (r - l > 1e-4)
            {
                double mid = (l + r) / 2;
                if (check(mid)) l = mid;
                else r = mid;
            }
            printf("%.2lf\n", r);
        }
    }
    return 0;
}