SPFA 和负环

关于 SPFA，以及……

~~……以及它死了~~，现在有意无意卡似乎已经成为 OI 出题界的常规操作了……

算法的流程如下：

遍历个点
对于当前的点，遍历它的所有出边，并获取出边相连的点
进行松弛操作，将设为
若终点的最短路长度不为正无穷，则找到最短路；否则整张图不连通

但是在第三步中，每个点的最短距离不一定能够被更新——只有上一次松弛成功的点连接的边，才有可能引起下一次更新。做一个优化，减少不必要的出队。引入了一个队列（类似于宽搜的队列），用来记录点的入队，避免不必要的松弛，具体如下：

void spfa(int s) {
    memset(dist, 0x3f, sizeof dist);

    queue<int> q;
    q.push(s);
    st[s] = true;
    dist[s] = 0;

    while (!q.empty()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            if (dist[j] > dist[t] + edges[i].w) {
                dist[j] = dist[t] + edges[i].w;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

~~长得和真的很像~~。

负环

负环，顾名思义，就是边权之和为负数的环。在中，有两种判负环的方式。

对每个点出队的次数进行计数，若某个点出队次数大于等于（点数），则存在负环
求出到达当前点的最短路所经过的边数，若边数大于等于则存在负环

实际情况我们更喜欢用第二种，考虑极端情况—— 个点构成一个大负环，那么程序在这个环上跑一圈，每个点均只出队一次；要想使某个点出队次，就要经过条边，会造成严重的性能浪费。相较之下，第二种方案只需要在这个环上绕一圈即可判断负环，效率是极高的。

以 P3385 负环模板题为例，给出修改后的核心代码：

bool spfa(int n) {
    memset(cnt, 0, sizeof cnt);
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);

    queue<int> q;
    q.push(1);
    st[1] = true;
    dist[1] = 0;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            if (dist[j] > dist[t] + edges[i].w) {
                dist[j] = dist[t] + edges[i].w;
                cnt[j] = cnt[t] + 1;
                if (cnt[j] == n) return false;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return true;
}

洛谷 P2850 [USACO06DEC] Wormhole G

题目地址：P2850

题目难度：普及+/提高

题目来源：USACO 2006

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。

John 的每个农场有条小路（无向边）连接着块地（从标号），并有个虫洞。

现在 John 希望能够从某块地出发，走过一条路径回到出发点，且同时也回到了出发时刻以前的某一时刻。请你告诉他能否做到。

输入格式：

输入的第一行是一个整数，代表测试数据的组数。

每组测试数据的格式如下：

每组数据的第一行是三个用空格隔开的整数，分别代表农田的个数，小路的条数，以及虫洞的个数。

每组数据的第到第行，每行有三个用空格隔开的整数，代表有一条连接与的小路，经过这条路需要花费的时间。

每组数据的第到第行，每行三个用空格隔开的整数，代表点存在一个虫洞，经过这个虫洞会到达点，并回到秒之前。

输出格式：

对于每组测试数据，输出一行一个字符串，如果能回到出发时刻之前，则输出 YES，否则输出 NO。

数据范围：

对于的数据，，，，，。

经典题。在题目中，我们不确定图的起点编号，图论中的经典技巧“虚拟源点”就派上用场了。虚拟源点是指新建一个原图中不存在的点，并把这个点向所有其他点连一条权值为的双向边，以实现多源汇最短路的求解。但实际操作中不一定需要真正的创建一个新点，可以从最短路初始的入队点入手——初始时先将号点全部入队。因为虚拟源点在初次松弛时，一定会遍历到所有相连点，即号点，然后松弛入队。因此开始将所有点加入队列和建立虚拟点并入队是等价的。

考虑把所有虫洞通道看作边权为的有向边，这道题就转化成了判断是否存在负环的题目。也就是说我们直接敲一遍求负环的模板，就可以通过此题。

#include <bits/stdc++.h>
#define N 510
#define M 3010
using namespace std;

struct Edge {
    int to, ne, w;
} edges[M << 1];

int h[N], idx = 0;
int dist[N], cnt[N];
bool st[N];

void add(int u, int v, int w) {
    idx++;
    edges[idx].to = v;
    edges[idx].ne = h[u];
    edges[idx].w = w;
    h[u] = idx;
}

bool spfa(int n) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    memset(cnt, 0, sizeof cnt);

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
        dist[i] = 0;
    }
    while (!q.empty()) {
        int t = q.front();
        q.pop();

        st[t] = false;
        for (int i = h[t]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            if (dist[j] > dist[t] + edges[i].w) {
                dist[j] = dist[t] + edges[i].w;
                cnt[j] = cnt[t] + 1;
                if (cnt[j] == n) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        memset(h, -1, sizeof h);
        idx = 0;

        int n, m, k;
        cin >> n >> m >> k;
        int u, v, w;
        for (int i = 1; i <= m; i++) {
            cin >> u >> v >> w;
            add(u, v, w);
            add(v, u, w);
        }
        for (int i = 1; i <= k; i++) {
            cin >> u >> v >> w;
            add(u, v, -w);
        }
        cout << (spfa(n) ? "YES" : "NO") << endl;
    }
    return 0;
}

洛谷 P2868 [USACO07DEC] Sightseeing Cows G

题目地址：P2868

题目难度：省选/NOI-

题目来源：USACO 2007

给你一张点边的有向图，第个点点权为，第条边边权为。

找一个环，设环上的点组成的集合为，环的边组成的集合为，最大化。

输入格式：

第一行是两个整数和

接下来行，每行一个整数代表

接下来行，每行三个整数，代表和之间有一条长为的边

输出格式：

一行一个数表示结果，保留两位小数

数据范围：

这道题需要用到分数规划相关知识，主要在对题目中算式的处理。根据题意可知，要求出一个环使得环中点权之和与边权之和比值最大。我们把环中的点权看作“性价比模型”里的“性能”，即；把边权看作“价格”，即。在分数规划中，当时，证明当前二分到的值小于正确答案；反之大于正确答案。根据这两条收缩二分区间，即可达到求解的效果。

在这道题里。考虑将上式变号，同乘，变为。如果我们把边的边权重定义为，就简化成“判断图上是否存在权值和为负的环”——负环的判断了。若形成负环，返回真，左区间收缩；反之收缩右区间。注意到负环的起始点并不确定，因此应用上面的超级源点思想来求解：

#include <bits/stdc++.h>
#define N 1010
#define M 5010
using namespace std;

struct Edge {
    int to, ne, w;
} edges[M << 1];
int h[N], idx = 0;
int p[N];
int cnt[N];
double dist[N];
bool st[N];
int L, P;
const double EPS = 1e-6;

void add(int u, int v, int w) {
    idx++;
    edges[idx].to = v;
    edges[idx].ne = h[u];
    edges[idx].w = w;
    h[u] = idx;
}

bool check(double mid) {
    memset(st, false, sizeof st);
    memset(cnt, 0, sizeof cnt);
    memset(dist, 127, sizeof dist);

    queue<int> q;
    for (int i = 1; i <= L; i++) q.push(i), st[i] = true, dist[i] = 0;

    while (!q.empty()) {
        int id = q.front();
        q.pop();

        st[id] = false;
        for (int i = h[id]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            double wfp = mid * edges[i].w - p[id];
            if (dist[j] > wfp + dist[id]) {
                dist[j] = wfp + dist[id];
                cnt[j] = cnt[id] + 1;
                if (cnt[j] == L) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(h, -1, sizeof h);

    cin >> L >> P;

    for (int i = 1; i <= L; i++) cin >> p[i];
    for (int j = 1; j <= P; j++) {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
    }
    double LEFT = 0, RIGHT = 1000;
    while (RIGHT - LEFT > EPS) {
        double mid = (LEFT + RIGHT) / 2;
        if (check(mid)) LEFT = mid;
        else RIGHT = mid;
    }
    cout << fixed << setprecision(2) << LEFT << endl;
    return 0;
}

SPOJ 2885 WORDRING - Word Rings

题目地址：SPOJ 2885

题目难度：省选/NOI-

如果字符串A的结尾两个字符与字符串B的开头两个字符相匹配，我们称A与B能 “ 相连 ” ( 注意：A与B能相连，不代表B与A能相连 )

当若干个串首尾 “ 相连 ” 成一个环时，我们称之为一个环串（一个串首尾相连也算）

我们希望从给定的全小写字符串中找出一个环串，使这个环串的平均长度最长
1
2
3
intercommunicational
 alkylbenzenesulfonate
 tetraiodophenolphthalein
如上例：第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串又能与第一个串相连。按此顺序连接，便形成了一个环串。

长度为 20+21+24=65 ( 首尾重复部分需计算两次 ) ，总共使用了3个串，所以平均长度是 65/3≈21.6666

输入格式：

多组数据每组数据第一行一个整数n，表示字符串数量接下来n行每行一个长度小于等于1000的字符串读入以n=0结束

输出格式：

若不存在环串，输出"No solution."。否则输出最长的环串平均长度。

Translated by @远藤沙椰

数据范围：

这道题让我们最大化一个比值，再次把目光放到分数规划上来。如同上一道题，这道题也可以转化为分数规划+判负环的算法求解。难点在于如何把一个一个的字符串建成图。

首先考虑把每个字符串当成一个点，如果两个字符串能首尾相接（直接判断首位两个字符），就连边，边权为两字符串长度之和。这样建图有没有什么不妥之处？

观察到数据范围，的极端情况是十万，假设我们有十万个完全相同的字符串，那么点数将是，两两连边，边数是。完全失败！

换一种思路，把首位两个字符当作点，把一个字符串拆成两点和一边（~~化学键~~），边权是该字符串的长度。此时的最大点数将是，最大边数是（字符串总数）。然后就可以用分数规划求解了。

从基本模型出发，得到。不难发现此时代表字符串的长度，代表所用字符串的数量（经过的边数）。求和是从的，每项展开得，新边权就是。像上一道题那样不等号两边同乘以，得到，就可以转化为一个判负环问题。判负环使用会稍慢（会TLE），这里改用来实现。

#include <bits/stdc++.h>

#define N 700
#define M 100010
#define distinct(a, b) ((a - 'a') * 26 + b - 'a')
#define recover(x) (string(1, char(x / 26 + 'a')) += char(x % 26 + 'a'))

using namespace std;

struct Edge {
    int to, ne, w;
} edges[M << 1];
int h[N], idx = 0;
const double EPS = 1e-6;
int n;
double dist[N];
bool st[N];

void add(int u, int v, int w) {
    idx++;
    edges[idx].to = v;
    edges[idx].ne = h[u];
    edges[idx].w = w;
    h[u] = idx;
}

bool spfa_dfs(int u, double d) {
    if (st[u]) return true;
    st[u] = true;
    for (int i = h[u]; ~i; i = edges[i].ne) {
        int j = edges[i].to;
        double wfp = d - edges[i].w;
        if (dist[j] > dist[u] + wfp) {
            dist[j] = dist[u] + wfp;
            if (spfa_dfs(j, d)) return true;
        }
    }
    st[u] = false;
    return false;
}

bool check(double d) {
    memset(dist, 0, sizeof dist);
    memset(st, false, sizeof st);

    for (int i = 0; i < 676; i++) {
        if (spfa_dfs(i, d)) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    while (cin >> n && n) {
        memset(h, -1, sizeof h);
        idx = 0;

        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            if (s.length() < 2) continue;
            add(distinct(s[0], s[1]), distinct(s[s.length() - 2], s[s.length() - 1]), s.length());
        }
        double L = 0, R = 1e5;
        while (R - L > EPS) {
            double mid = (L + R) / 2;
            if (check(mid)) L = mid;
            else R = mid;
        }
        if (L > EPS) cout << L << endl;
        else cout << "No solution." << endl;
    }
    return 0;
}

相似题目：UVA 11090、P3199、P3288