最短路问题（二）

floyd 任意两点最短路径

floyd 算法能够求出任意两点 $(i, j)$ 之间的最短路径
根据动态规划的思想，对编号为 $k$ 这个节点，我们有两种决策，选还是不选这个点
由此根据考虑编号为 $k$ 的节点作为 dp 的阶段，从 $k-1$ 到 $k$ 的转移
需要决策是否经过编号为 $k$ 的节点

$$f(k, i, j) = \min (f(k-1, i, j), f(k-1, i, k) + f(k-1, k, j))$$

如果用邻接矩阵存图，$A(i, j)$ 表示边 $(i, j)$ 的长度，那么 dp 初始化为
$f(0, i, j) = A(i, j)$

传递闭包

不妨用 $f(i, j) = 1$ 表示 $i$ 和 $j$ 之间有关系，$f(i, j) = 0$ 表示没有关系
特别地，$f(i, i) = 1$，可以用 floyd 算法解决传递闭包问题

const int maxn = 1e3 + 10;
bool f[maxn][maxn];
int n;
int main() {
    // ...
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j] |= (f[i][k] & f[k][j]);
    // ...
}

Sorting It All Out

很显然这是一个有向图传递闭包的问题，对于 $i < j$ 的不等式，令 $f(i, j) = 1$
$i > j$ 转为 $j < i$ 处理，令 $f(j, i) = 1$

执行 floyd 传递闭包，如果存在 $f(i, j) = 1$ 并且 $f(j, i) = 1$，那么不等式存在矛盾
如果 $f(i, j) = 0$ 并且 $f(j, i) = 0$ 说明 $(i, j)$ 之间的大小关系不确定
此外如果 $f(i, j), \ f(j, i)$ 仅有一个为 $1$，那么能够确定变量之间的大小关系

需要输出不等式之间的大小关系，由于是一个 DAG，可以考虑使用拓扑排序输出

const int maxn = 26 + 10;
int G[maxn][maxn], f[maxn][maxn], deg[maxn];
int n, m;

void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                f[i][j] |= (f[i][k] & f[k][j]);
        }
    }
}

int conflict() {
    for (int i = 0; i < n; i++) {
        if (f[i][i]) return 1;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            if (f[i][j] && f[j][i]) return 1;
        }
    }
    return 0;
}

int sure() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            if (f[i][j] == 0 && f[j][i] == 0) return 0;
        }
    }
    return 1;
}

void topo() {
    queue<int> que;
    string res = "";
    for (int i = 0; i < n; i++) if (deg[i] == 0) que.push(i);

    while (que.size()) {
        auto u = que.front(); que.pop();
        res += ('A' + u);

        for (int v = 0; v < n; v++) if (G[u][v] && --deg[v] == 0) que.push(v); 
    }
    printf("%s", res.c_str());
    printf(".\n");
}

void init() {
    memset(G, 0, sizeof G);
    memset(f, 0, sizeof f);
    memset(deg, 0, sizeof deg);
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &n, &m) == 2 && n) {
        init();

        int st = 0, t = 0;
        // -1 conflict, 1 ok, 0 not sure

        for (int i = 0; i < m; i++) {
            char str[10];
            scanf("%s", str);

            if (st != 0) continue;

            int u = str[0] - 'A', v = str[strlen(str)-1] - 'A';
            f[u][v] |= 1, G[u][v] = 1, deg[v]++;

            floyd();

            if (conflict()) st = -1;
            else if (sure()) st = 1;
            t = i;
        }

        // get ans
        if (st == -1) printf("Inconsistency found after %d relations.\n", t+1);
        else if (st == 1) {
            printf("Sorted sequence determined after %d relations: ", t+1);
            topo();
        }
        else puts("Sorted sequence cannot be determined.");
    }
}

无向图最小环

Sightseeing Trip

同样套用 floyd 算法
在第 $k$ 个阶段，$f(i, j)$ 表示编号为 $\{0\cdots k-1\}$ 节点集合中
$(i, j)$ 之间的最短路，用 $\min(f(i,j) + e(i, k) + e(k, j), res)$ 更新答案 $res$

然后再将 $k$ 这个点纳入集合中，用 $\textbf{floyd}$ 算法更新 $f(i, j)$ 的最短路径
$f(i, j)$ 更新完之后，就考虑了 $\{0\cdots k\}$ 节点集合的最短路

继续往下迭代，即可得到最优解

特别注意的是，如图中所示，$i, j$ 两个节点的编号 $< k$

const int maxn = 200 + 10, inf = 0x3f3f3f3f;
int n, m;
int e[maxn][maxn], f[maxn][maxn], res = inf;
int pos[maxn][maxn];

vector<int> path;

void get_path(int x, int y) {
    if (pos[x][y] == 0) return;
    int k = pos[x][y];

    get_path(x, k);
    path.push_back(k);
    get_path(k, y);
}

void floyd() {
    memcpy(f, e, sizeof e);
    memset(pos, 0, sizeof pos);
    res = inf;
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i < k; i++) for (int j = i+1; j < k; j++) {
            if ((ll)f[i][j] + e[j][k] + e[k][i] < res) {
                res = f[i][j] + e[j][k] + e[k][i];

                path.clear();
                path.push_back(i);
                get_path(i, j);
                path.push_back(j);
                path.push_back(k);
            }
        }

        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
            if (f[i][k] + f[k][j] < f[i][j]) {
                f[i][j] = f[i][k] + f[k][j];
                pos[i][j] = k;
            }
        }
    }
}

void init() {
    memset(e, inf, sizeof e);
    for (int i = 0; i <= n; i++) e[i][i] = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    init();
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[u][v] = e[v][u] = min(e[u][v], w);
    }

    // then solve

    floyd();
    if (res == inf) puts("No solution.");
    else {
        for (auto x : path) printf("%d ", x);
        printf("\n");
    }
}

floyd 与广义矩阵运算

给定一张无向图，求从起点到终点恰好经过 $n$ 条边（可以重复经过）的最短路

在 floyd 算法执行过程中，最开始阶段 $A_1(i, j) = e(i, j)$，即表示 $i \to j$ 仅经过一条边 $(i, j)$ 的最短路
而 floyd 方程中，$A_2(i, j) = \displaystyle\min_{1 \leqslant k \leqslant n} \{A_1(i, k) + A_1(k, j)\}$
此时我们枚举了 $i \to k \to j$，$A_2(i, j)$ 表示 $i \to j$ 经过了 $2$ 条边的最短路

以此类推，用 $A_m(i, j)$ 表示恰好经过 $m$ 条边的最短路，那么

$$A_{m+r}(i, j) = \min_{1 \leqslant k \leqslant n} \{A_{m}(i, k) + A_{r}(k, j)\}$$

最后答案是求 $A_n(s, t)$，可以用矩阵快速幂来求解，不过矩阵乘法的过程，需要改成

$$C(i, j) = \min_{1 \leqslant k \leqslant n} \{A(i, k) + B(k, j)\}$$

const int maxn = 100 + 10, inf = 0x3f3f3f3f;
map<int, int> M;
int n, N, m, s, t, G[maxn][maxn], idx = 0;

typedef vector<vector<int> > Matrix;

Matrix get_matrix() {
    Matrix res(maxn, vector<int>(maxn, inf));
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
        res[i][j] = G[i][j];
    }
    return res;
}

Matrix matrix_mul(const Matrix &A, const Matrix &B) {
    Matrix res(maxn, vector<int>(maxn, inf));
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= n; k++)
            res[i][j] = min(res[i][j], A[i][k] + B[k][j]);
    }
    return res;
}


void solve(Matrix &A) {
    N--;
    Matrix res = A;
    for (; N; N >>= 1) {
        if (N & 1) res = matrix_mul(res, A);
        A = matrix_mul(A, A);
    }
    cout << res[M[s]][M[t]] << endl;
}

void init() {
    M.clear();
    memset(G, inf, sizeof G);
    idx = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d%d", &N, &m, &s, &t);
    init();

    // get data
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d%d%d", &z, &x, &y);
        int u = M[x] ? M[x] : (M[x] = ++idx);
        int v = M[y] ? M[y] : (M[y] = ++idx);

        G[u][v] = G[v][u] = z;
    }
    n = idx;
    Matrix A = get_matrix();

    solve(A);
}

最短路和 dp

Adventure Of Super Mario

类似背包问题，容易想到的是当前使用了 $k$ 次魔法鞋，作为 dp 的一个状态维度
$dp(v, k)$ 表示当前位于节点 $v$ 处，并且使用了 $k$ 次魔法鞋，从起点到当前位置所耗费的最短时间

对于 $\forall \ k \in [0, K]$，当前在节点 $v$ 处，根据是否使用魔法鞋存在 $2$ 种状态转移
$(u, v)$ 的状态转移如下，其中 $u \in \text{prev}(v)$，在节点 $v$ 的前驱节点集合中
$u \in [1, v-1]$

• $dp(v, k) = \displaystyle \min_{u \in [1, v-1]} \{dp(u, k) + f(u, v)\}$，其中 $f(u, v)$ 一定是 $u\to v$ 的最短路径
  这可以通过 floyd 算法预处理来求出
• $dp(v, k) = \displaystyle \min_{u \in [1, v-1]} \{dp(u, k-1)\}$，约束条件为
  $f(u, v) \leqslant L$ 并且 $(u, v)$ 最短路径上的节点编号 $\leqslant A$
  最短路径上的节点编号不超过 $A$，正好可以用 $\text{floyd}$ 算法
  $\text{floyd}$ 算法执行到 $k$ 这个阶段并且完成 $f(i, j) = \min (f(i, k) + f(k, j))$ 这个松弛操作的时候
  $f(i, j)$ 表示 $(i, j)$ 经过编号不超过 $k$ 的节点的最短路径
  上述约束条件可以在 floyd 算法执行的时候求出，具体来说
  $f(i, j) \leqslant L \ \textbf{and} \ k \leqslant A$

最后考虑 dp 的初始状态和终点
初始状态，注意到状态表示 $dp(u, k)$ 有 $2$ 个维度
$\forall k \in [0, K]: \quad dp(s, k) = 0$
$\forall u \in V: \quad dp(u, 0) = f(s, u)$

最后的答案为 $\displaystyle\min_{k \in [0, K]} dp(t, k)$

const int maxn = 100 + 10, inf = 0x3f3f3f3f;
int A, B, M, L, K, n, s, t;

int f[maxn][maxn];

void init() {
    memset(f, inf, sizeof f);
    n = A+B;
    for (int i = 1; i <= n; i++) f[i][i] = 0;
    s = 1, t = A+B;
}

int can[maxn][maxn];

void floyd() {
    memset(can, 0, sizeof can);
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
            if (f[i][j] > f[i][k] + f[k][j]) {
                f[i][j] = f[i][k] + f[k][j];
            }
            if (k <= A && f[i][j] <= L) can[i][j] = 1;
        }
    }
}

int dp[maxn][maxn];
void solve() {
    memset(dp, inf, sizeof dp);
    for (int i = 0; i <= K; i++) dp[s][i] = 0;
    for (int u = 1; u <= n; u++) dp[u][0] = f[s][u];

    for (int v = 1; v <= n; v++) {
        for (int k = 1; k <= K; k++) {
            _for(u, 1, v) {
                if (can[u][v]) dp[v][k] = min(dp[v][k], dp[u][k-1]);
                dp[v][k] = min(dp[v][k], dp[u][k] + f[u][v]);
            }
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;

    while (cas--) {
        cin >> A >> B >> M >> L >> K;
        init();

        // get graph
        for (int i = 0; i < M; i++) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            f[x][y] = f[y][x] = min(f[x][y], z);
        }

        // floyd and dp

        floyd();
        solve();
        int ans = inf;
        for (int i = 0; i <= K; i++) ans = min(ans, dp[n][i]);
        cout << ans << endl;
    }
}

最短路建图：拆点

Full Tank?

要求从 $s \to t$ 的最便宜路径，不难想到将油价作为边权，由于油箱容量 $c \in [0, C]$
油箱容量 $c$ 也应该作为状态维度
$(u, c)$ 二元组表示当前汽车在点 $u$ 处，并且油箱有油 $c$ 单位

对于当前点 $v$，根据在 $v$ 处是否加油，存在 $2$ 种 $(u, v)$ 的状态转移

• $(u, \ c+d(u, v)) \xrightarrow{0} (v, c)$，此时 $c + d(u, v) \leqslant C$
• $(v, c-1) \xrightarrow{p_v} (v, c)$，在 $(v, c-1)$ 和 $(v, c)$ 间连一条权值为 $p_v$ 的边
  实际上这里将 $v$ 这个点拆成 $2$ 个状态，当然 $c-1 \geqslant 0 \ \textbf{and} \ c \leqslant C$

这样可以以 $(s, 0)$ 作为起点 $S$，执行 $\text{dijkstra}$，求出单源最短路
$\forall u, c: \quad d[(u, c)]$，最后答案就是 $\displaystyle\min_{c \in [0, C]} d(t, c)$

如果用哈希实现，将结构体作为 $key$，代码如下

class A {
public:
    int u, c;
    A(int u = 0, int c = 0) : u(u), c(c) {}
    bool operator< (const A &rhs) const {
        return u < rhs.u || (u == rhs.u && c < rhs.c);
    }
};

struct hashfun {
    std::size_t operator() (const A &a) const {
        return ( (hash<int>()(a.u))
            ^ (hash<int>()(a.c) << 1) );
    }
};

struct eq {
    bool operator() (const A &lhs, const A &rhs) const {
        return lhs.u == rhs.u && lhs.c == rhs.c;
    }
};

unordered_map<A, int, hashfun, eq> mp;

int get(const A &a) {
    return mp[a] ? mp[a] : (mp[a] = ++n);
}

如果本例先建出隐式图，再进行 $\text{dijkstra}$ 的话，每次都 $\text{build}$ 会造成算法开销过大
实际上，我们在 $\text{dijkstra}$ 的时候没有必要把整张图都建出来，因为有一些节点根本用不到
$\text{dijkstra}$ 的时候优先队列维护二元组 $(d[(u, c)], (u, c))$，对于当前状态 $(u, c)$
检查 $\forall \ v: \ (u, v) \in E$，对于边 $\forall v : \ (u, v)$，存在转移

• $(u, c) \xrightarrow{p_u} (u, c+1)$，当然 $c+1 \leqslant C$，此时转移的权值代价为 $p_u$
• $(u, c) \xrightarrow{0} (v, c-e(u, v))$，必须 $c-e(u, v) \geqslant 0$，转移权值为 $0$

起点为 $S = (s, 0)$，最后的答案为
$\forall c: \ \displaystyle\min_{c \in [0, C]}d[(t, c)]$
另外，由于 $\text{dijkstra}$ 不会有负权边，所以取出二叉堆堆顶元素 $(u, c)$，如果发现 $u = t$
那么应该立即结束 $\text{dijkstra}$，不需要继续扩展了，后续点的代价 $d$ 一定比 $d[(u, c)]$ 大
后续节点也用不到

const int maxn = 2e3 + 10, inf = 0x3f3f3f3f;
const int maxm = 2e4 + 10;

int n, m, C, s, t, p[maxn], res = inf;

namespace Graph {
    int idx = 1;
    int head[maxn], ver[maxm], e[maxm], ne[maxm];

    void add(int x, int y, int z) {
        ver[++idx] = y, e[idx] = z, ne[idx] = head[x], head[x] = idx;
    }

    void init() {
        idx = 1;
        memset(head, 0, sizeof head);
    }
};

class A {
public:
    int u, c;
    A(int u, int c) : u(u), c(c) {}
    bool operator< (const A &rhs) const {
        return u < rhs.u || (u == rhs.u && c < rhs.c);
    }
};

struct hashfun {
    int operator() (const A &a) const {
        return a.u * 1003 + a.c;
    }
};

struct eqfun {
    bool operator() (const A &lhs, const A &rhs) const {
        return lhs.u == rhs.u && lhs.c == rhs.c;
    }
};

unordered_map<A, int, hashfun, eqfun> mp;
int tot = 0;

inline int get(const A &a) {
    return mp[a] ? mp[a] : (mp[a] = ++tot);
}

const int N = 1e5 + 10;
int d[N], vis[N];
typedef pair<int, A> PII;
// (d[ states ], (u, c))

void dijkstra() {
    using namespace Graph;
    memset(d, inf, sizeof d);
    memset(vis, 0, sizeof vis);
    res = inf;
    
    priority_queue<PII, vector<PII>, greater<PII> > q;
    int ss = get(A(s, 0));
    d[ss] = 0;
    q.push(PII(d[ss], A(s, 0)));

    while (q.size()) {
        int D = q.top().first;
        auto x = q.top().second; q.pop();

        if (x.u == t) {
            res = min(res, D);
            return;
        }

        int sx = get(x);
        if (vis[sx]) continue;
        vis[sx] = true;

        if (x.c + 1 <= C) {
            A y(x.u, x.c+1);
            int sy = get(y);

            if (d[sy] > D + p[x.u]) {
                d[sy] = D + p[x.u];
                q.push(PII(d[sy], y));
            }
        }

        for (int i = head[x.u]; i; i = ne[i]) {
            int v = ver[i];
            if (x.c >= e[i]) {
                A y(v, x.c-e[i]);
                int sy = get(y);

                if (d[sy] > D + 0) {
                    d[sy] = D;
                    q.push(PII(d[sy], y));
                }
            }
        }
    }
    return;
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;
    using namespace Graph;
    init();

    for (int i = 0; i < n; i++) scanf("%d", &p[i]);
    while (m--) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z), add(y, x, z);
    }

    // query and dijkstra
    int q;
    cin >> q;
    while (q--) {
        scanf("%d%d%d", &C, &s, &t);
        dijkstra();

        if (res == inf) puts("impossible");
        else printf("%d\n", res);
    }
}