算法提高课第三章负环

spfa算法可以求出图中是否存在负环

一般求解负环有两种方法

• 统计每个点入队的次数，如果有的点入队次数大于等n，那么存在负环
• 统计到每个点的最短路径长度，如果长度大于等于n，那么存在负环

spfa算法的几个注意点

• 求解是否存在负环与dist初始值无关
• 负环求最短路
• 正环求最长路
• 将队列换成栈有机会很快找到环路
• 根据经验，在更新了很多次路径以后没有跳出循环，可以认为存在环。

01规划问题，一般是求分数的最大值或者最小值，可以利用二分的思想转化为求解图上的环路问题

904. 虫洞 - AcWing题库

/*
 * @author: wangqianyv
 * @Date: 2021-12-22 20:10:20
 * @LastEditTime: 2021-12-22 20:47:25
 * @Description: 
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 510, M = 5210;
int e[M], w[M], h[N], ne[M];
int dist[N];
bool st[N];
int cnt[N];
int idx = 0;
int n;
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa()
{
    memset(dist, 0, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        q.push(i); //虚拟源点相连的所有边
        st[i] = true;
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[u] + w[i])
            {
                dist[j] = dist[u] + w[i];
                cnt[j] = cnt[u] + 1; //最短路的长度
                if (cnt[j] >= n)
                    return true; //最短路长度为n，有n+1个点
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(h, -1, sizeof h);
        idx = 0;
        int m, p;
        cin >> n >> m >> p;
        for (int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
            add(b, a, c);
        }
        for (int i = 0; i < p; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, -c);
        }
        if (spfa())
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

361. 观光奶牛 - AcWing题库

/*
 * @author: wangqianyv
 * @Date: 2021-12-22 20:48:55
 * @LastEditTime: 2021-12-22 21:18:12
 * @Description: 
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
//01规划问题，二分找答案
const int N = 1100, M = 5500;

int n, m;
int f[N], t[N], e[M], ne[M], h[N], w[M];
int idx;
double dist[N];
int cnt[N];
bool st[N];
double eps = 1e-4;
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa(double x)
{
    memset(dist, 0, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[u] - f[j] + x * w[i]) //加上j点的点权减去i边的边权
            {

                dist[j] = dist[u] - f[j] + x * w[i];
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= n)
                    return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++)
        cin >> f[i];
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    double l = 1 / 1000, r = 1000;
    double ans = 0;
    while (r - l >= eps)
    {
        double mid = (l + r) / 2;
        if (spfa(mid)) //有负环，要变大
        {
            l = mid + eps;
            ans = max(ans, mid);
        }
        else
        {
            r = mid - eps;
        }
    }
    printf("%.2f", ans);
}

1165. 单词环 - AcWing题库

/*
 * @author: wangqianyv
 * @Date: 2021-12-22 21:28:52
 * @LastEditTime: 2021-12-22 21:58:45
 * @Description: 
 * 
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
const int N = 27 * 27, M = 100010;
//把两个字母看成是一个一个点
int n, idx;
double eps = 1e-4;
int h[N], w[M], e[M], ne[M];
double dist[N];
int st[N], cnt[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa(double x)
{
    memset(dist, 0, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    stack<int> q;
    for (int i = 0; i < 26 * 26; i++)
    {
        q.push(i);
        st[i] = true;
    }
    int sum = 0;
    while (q.size())
    {
        int u = q.top();
        q.pop();
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[u] + x - w[i])
            {
                sum ++;
                if(sum > 2000) return true;
                dist[j] = dist[u] + x - w[i];
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= 26 * 26)
                    return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main()
{
    while (scanf("%d", &n), n)
    {
        char str[1010];
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", str);
            int len = strlen(str);
            if (len >= 2)
            {
                int left = (str[0] - 'a') * 26 + str[1] - 'a';
                int right = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
                add(left, right, len);
            }
        }
        if (!spfa(0)) //没有负环，那么无解
            puts("No solution");
        else
        {
            double l = 1, r = 1000;
            double ans = 0.1;
            while (r - l >= eps)
            {
                double mid = (l + r) / 2;
                if (spfa(mid))
                {
                    ans = max(ans, mid);
                    l = mid + eps;
                }
                else
                    r = mid - eps;
            }
            printf("%f\n", ans);
        }
    }
}