图算法和图模型(五)

这篇博文重点讲状态依赖的最短路问题
以spfa，负环判断为主
另外还讲了一些最短路算法在实践中的应用

状态依赖的SPFA算法

电梯调度问题

$(x, j)$ 表示电梯当前在 $x$ 层，手柄位置为 $j$
$\text{spfa queue statues}$$:= vis(x, j)$

$\textbf{for}\ \forall i \in [1, m] \leftrightarrow \text{next position}$
$~~~~~~$$w=|i-j|+2|C(i)|$

$$\begin{gathered} d(x+C[i], i) = \min\{d(x+C[i],i), d(x,j)+w\} \\ \ \\ \text{run spfa()} \end{gathered}$$

spfa算法注意点
在计算下一个状态的时候
判断

!inq[next]

if(D[next] > D[cur] + w) {
    if(!inq[next]) {
        que.push(next);
        inq[next] = 1; 
    }
}

#define MPR(a, b) make_pair(a, b)

const int maxn = 1000 + 5;
const int maxm = 20 + 5;
const int inf = 0x3f3f3f3f;
int n, m;

int D[maxn][maxm], inq[maxn][maxm];
typedef pair<int, int> PII;
int C[maxn];

// == run spfa ==
void initSpfa() {
    Set(inq, 0);
    Set(D, inf);
}

void spfa(int st_x, int st_j) {
    queue<PII> que;
    que.push(MPR(st_x, st_j));
    D[st_x][st_j] = 0;
    inq[st_x][st_j] = 1;

    while (!que.empty()) {
        int x = que.front().first;
        int j = que.front().second;
        que.pop();
        inq[x][j] = 0;

        _rep(i, 1, m) {
            int nx = x + C[i];
            int w = abs(i - j) + 2 * abs(C[i]);
            if(nx < 1 || nx > n) continue;

            if(D[nx][i] > D[x][j] + w) {
                D[nx][i] = D[x][j] + w;
                if(!inq[nx][i]) {
                    que.push(MPR(nx, i));
                    inq[nx][i] = 1;
                }
            }
        }
    }
}
// == spfa finsihed ==

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    int pos = 0;
    _rep(i, 1, m) {
        scanf("%d", &C[i]);
        if(C[i] == 0) pos = i;
    }

    // then spfa
    initSpfa();
    spfa(1, pos);

    int ans = inf;
    _rep(i, 1, m) ans = min(ans, D[n][i]);

    if(ans == inf) puts("-1");
    else printf("%d\n", ans);
}

floyd路径统计

algorithm

$c(i, j)$ 用来记录 $i \rightarrow j$ 最短路的条数

• $\textbf{for} \ \forall e(u, v) \in E(G)$
  $~~~~~~$$\text{init}: \ c(u, v) = 1$

• $\textbf{if} \quad d(u,v) > d(u, k) + d(k, v)$
  $~~~~~~$$c(u, v) = c(u, k) \cdot c(k, v)$

  $\textbf{if} \quad d(u, v) = d(u, k) + d(k, v)$
  $~~~~~~$$c(u, v) += c(u, k) \cdot c(k, v)$

• 经过 $k$ 的最短路，满足 $\textbf{floyd}$ 方程
  $\forall (i, j), i \neq j, \quad d(i,j) = d(i,k)+d(k, j)$

const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
int n, m;

int d[maxn][maxn];
ll c[maxn][maxn];
double ans[maxn];

void initFloyd() {
    Set(d, inf);
    _rep(i, 0, n) d[i][i] = 0;

    Set(c, 0);
    Set(ans, 0.0);
}

void floyd() {
    _rep(k, 1, n) _rep(i, 1, n) _rep(j, 1, n) {
        if(i != j && k != i && k != j) {
            if(d[i][j] > d[i][k] + d[k][j]) {
                d[i][j] = d[i][k] + d[k][j];
                c[i][j] = 1ll * c[i][k] * c[k][j];
            }
            else if(d[i][j] == d[i][k] + d[k][j]) {
                c[i][j] += 1ll * c[i][k] * c[k][j];
            }
        }
    }
}

void solve() {
    _rep(k, 1, n) _rep(i, 1, n) _rep(j, 1, n) {
        if(i != j && k != i && k != j) {
            if(d[i][j] == d[i][k] + d[k][j]) {
                ans[k] += (double) c[i][k] * c[k][j] / c[i][j];
            }
        }
    }
    _rep(i, 1, n) printf("%.3lf\n", ans[i]);
}


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

    initFloyd();

    _for(i, 0, m) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        d[x][y] = d[y][x] = z;
        c[x][y] = c[y][x] = 1ll;
    }

    floyd();
    solve();
}

Dijkstra和DAG上的dp

$\textbf{algorithm}$

• $\text{run dijkstra()}$
  $~~~~~~$$\textbf{we}\ \textbf{get} \ \forall u, \ \textbf{D(u)}$
• $\textbf{dp}(st\leftarrow ed) ,\ \textbf{begin:} \ \textbf{consider} \ \textbf{ed}$
  $~~~~~~$$f(ed) = 1, f(v/ed) = 0$
  $~~~~~~$$\textbf{sort} \ \textbf{according} \ \textbf{to} \ D[u]\rightarrow ord[\cdots], \ ord_0 = ed$
  $~~~~~~$$\textbf{now} \ D(ord_0)=0, D(ord_1), D(ord_2) \uparrow \cdots$
  $~~~~~~$$\textbf{for} \ \forall x = ord_i \ \textbf{for} \ \forall e(x, y)$
  $~~~~~~$$~~~~$$\textbf{if} \ D(y) > D(x), f(y) += f(x)$
  $~~~~~~$$\text{ans is } f(st)$

$\text{in this case, run dp() in } \textbf{every} \ \textbf{node}$

• $\textbf{dp}(st\rightarrow ed), \textbf{begin:} \ \textbf{consider} \ \textbf{dp(st,} \ \textbf{ed)}$
  $~~~~~~$$\textbf{init} \ \textbf{set} \ f[\cdots] \leftarrow -1$
  $~~~~~~$$\textbf{dp}(x, ed)$
  $~~~~~~$$~~~~$$\textbf{if} \ x = ed, \text{return } 1$
  $~~~~~~$$~~~~$$\textbf{if} \ f(x) \geqslant 0, \text{found ans, return } f(x)$
  $~~~~~~$$~~~~$$\textbf{let} \ f(x) = 0, \textbf{for} \ \forall e(x, y)$
  $~~~~~~$$~~~~$$~~~~$$\textbf{if} \ D(y) < D(x), f(x) +=dp(y, ed)$
  $~~~~~~$$~~~~$$\text{return } f(x)$

$\text{run dp() recursive }$

const int maxn = 1000 + 10;
const int inf = 0x3f3f3f3f;
int n, m;

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
    int to, weight;
    Edge() {}
    Edge(int t, int w) : to(t), weight(w) {}
};

vector<Edge> edges;

void initG() {
    _for(i, 0, maxn) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(v, w));
    G[u].push_back(edges.size() - 1);
}

class Node {
public:
    int u, dist;
    bool operator< (const Node& rhs) const {
        return dist > rhs.dist;
    }
    Node() {}
    Node(int u, int d) : u(u), dist(d) {}
};
// == Graph finished ==

// == dijkstra ==
int D[maxn], vis[maxn];

void initDij(int st) {
    Set(D, inf);
    D[st] = 0;
    Set(vis, 0);
}

void dijkstra(int st) {
    initDij(st);
    priority_queue<Node> que;
    que.push(Node(st, 0));

    while (!que.empty()) {
        int x = que.top().u;
        que.pop();
        if(vis[x]) continue;
        vis[x] = 1;

        _for(i, 0, G[x].size()) {
            const Edge& e = edges[G[x][i]];
            int y = e.to;

            if(D[y] > D[x] + e.weight) {
                D[y] = D[x] + e.weight;
                que.push(Node(y, D[y]));
            }
        }
    }
}
// == dijkstra finished ==

// == dp ==
inline bool cmp(int a, int b) {
    return D[a] < D[b];
}
int ord[maxn];
int f[maxn];
void initDP(const int ed) {
    _rep(i, 1, n) ord[i] = i;
    sort(ord + 1, ord + 1 + n, cmp);
    //assert(ed == ord[1]);

    Set(f, 0);
    f[ed] = 1;
}

void dp(const int st) {
    _rep(i, 1, n) {
        int x = ord[i];
        _for(j, 0, G[x].size()) {
            int y = edges[G[x][j]].to;
            if(D[y] > D[x]) f[y] += f[x];
        }
    }
    printf("%d\n", f[st]);
}

void initDP() {
    Set(f, -1);
}
int dp(int x, const int ed) {
    if(x == ed) return 1;
    if(f[x] >= 0) return f[x];

    f[x] = 0;
    _for(i, 0, G[x].size()) {
        int y = edges[G[x][i]].to;
        if(D[y] < D[x]) f[x] += dp(y, ed);
    }
    return f[x];
}
// == dp finsiehd ==

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &n, &m) == 2 && n) {
        initG();
        _for(i, 0, m) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            addEdge(x, y, z);
            addEdge(y, x, z);
        }

        // run dijkstra
        dijkstra(2);

        // then dp
        initDP(2);
        dp(1);

        //initDP();
        //printf("%d\n", dp(1, 2));
    }
}

最短路树

$\textbf{algorithm:} \ e(x, u):=p(u) \ \textbf{is} \ \textbf{the} \ \textbf{forward} \ \textbf{arc(前向弧)}$
$\textbf{run} \ dijkstra() \text{ and record } p()$

$$\textbf{Dijkstra-Tree} \ \textbf{:=} \bigcup\limits_{p(u) \in path}e(p(u))$$

• $\textbf{init:} \quad W(u, v) = \bigcup\limits_{weights}w(u, v)$
  $\text{multiple edges, } idx(u, v) := \text{edge number}$
  $used(src, u, v):= \text{ run dijkstra}(src), e(u, v)\text{ is Tree-edge or not}$

• $\textbf{for} \ \forall src \in V(G)$
  $~~~~~~$$\textbf{run}\ \textbf{Dijkstra}(src) \rightarrow \text{ mark } p(\cdots)$
  $~~~~~~$$\textbf{for}\ \forall u \in V(G), \forall e(u, v) \in \textbf{Dijkstra-Tree}(G)$
  $~~~~~~$$~~~~$$C(src) = \sum_u D(u), \text{ mark } used(src, u, v)$
  $\textbf{ans} = \sum C(src)$

• $\textbf{consider} \ \textbf{delete} \ \textbf{operation}$
  $~~~~~~$$\textbf{del}(u, v)\Rightarrow w(u, v) = 0 \ \textbf{or} \ w(u, v) = W(u, v)[2, 3, \cdots]$
  $~~~~~~$$\textbf{for} \ \forall src \in V(G)$
  $~~~~~~~~~~$$\textbf{if} \ used(src, u, v)=0, \ \textbf{ans} \ = \sum C(src)$
  $~~~~~~~~~~$$\textbf{else} \ \text{rebuild Dijkstra-Tree}$
  $~~~~~~~~~~~~~~$$\text{run Dijkstra}(src)$
  $~~~~~~~~~~~~~~$$\textbf{for} \ \forall u \in V(G)$
  $~~~~~~~~~~~~~~~~~~$$\textbf{ans} = \sum D(u)$

  $\textbf{reset} \ w(u, v) = W(u, v)[0]$

UVA1416

const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
int n, m, L;

vector<int> W[maxn][maxn];
int used[maxn][maxn][maxn];
int idx[maxn][maxn];

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
    int from, to, weight;
    Edge() {}
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

class Node {
public:
    int u, dist;
    Node() {}
    Node(int u, int d) : u(u), dist(d) {}
    bool operator< (const Node& rhs) const {
        return dist > rhs.dist;
    }
};

vector<Edge> edges;

void initG() {
    _for(i, 0, maxn) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(u, v, w));
    G[u].push_back(edges.size() - 1);
    idx[u][v] = edges.size() - 1;
}
// == Graph finished ==

// == Dijkstra ==
int p[maxn];
int D[maxn], vis[maxn];

void initDij(int st) {
    Set(p, 0);
    Set(vis, 0);
    Set(D, inf);
    D[st] = 0;
}

void dijkstra(int st) {
    initDij(st);
    priority_queue<Node> que;
    que.push(Node(st, 0));

    while (!que.empty()) {
        int x = que.top().u;
        que.pop();
        if(vis[x]) continue;
        vis[x] = 1;

        _for(i, 0, G[x].size()) {
            const Edge& e = edges[G[x][i]];
            int y = e.to;

            if(e.weight > 0 && D[y] > D[x] + e.weight) {
                D[y] = D[x] + e.weight;
                p[y] = G[x][i];
                que.push(Node(y, D[y]));
            }
        }
    }
}
// == Dijkstra finished ==

// == solver ==
int C[maxn];

void initCal() {
    Set(C, 0);
}

int cal() {
    initCal();

    int ans = 0;
    _rep(st, 1, n) {
        dijkstra(st);
        _rep(v, 1, n) {
            if(v != st) {
                int u = edges[p[v]].from;
                used[st][u][v] = used[st][v][u] = 1;
            }
            C[st] += (D[v] == inf ? L : D[v]);
        }
        ans += C[st];
    }
    return ans;
}


int del(int u, int v) {
    Edge& e1 = edges[idx[u][v]];
    Edge& e2 = edges[idx[v][u]];;

    if(W[u][v].size() == 1) e1.weight = e2.weight = 0;
    else if(W[u][v].size() > 1) e1.weight = e2.weight = W[u][v][1];

    int ans = 0;
    _rep(st, 1, n) {
        if(used[st][u][v] == 0) ans += C[st];
        else {
            dijkstra(st);
            _rep(i, 1, n) ans += (D[i] == inf ? L : D[i]);
        }
    }

    e1.weight = e2.weight = W[u][v][0];
    return ans;
}
// == solver finsihed ==

void init() {
    _for(i, 0, maxn) _for(j, 0, maxn) W[i][j].clear();
    Set(used, 0);
    Set(idx, 0);
}

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

        // build graph
        _for(i, 0, m) {
            int u, v, s;
            scanf("%d%d%d", &u, &v, &s);
            W[u][v].push_back(s);
            W[v][u].push_back(s);
        }
        _rep(i, 1, n) _rep(j, i + 1, n) {
            if(W[i][j].size()) {
                sort(W[i][j].begin(), W[i][j].end());

                addEdge(i, j, W[i][j][0]);
                addEdge(j, i, W[i][j][0]);
            }
        }
        // build finished

        // solve the problem
        int c1 = cal();
        int c2 = -1;
        _rep(i, 1, n) _rep(j, i + 1, n) if(W[i][j].size()) {
            c2 = max(c2, del(i, j));
        }

        printf("%d %d\n", c1, c2);
    }
}

Dijkstra杂题，路径输出

$\textbf{ceil}(x) := \geqslant x \textbf{(离x最近的整数)}$
常常用来处理以下问题，比如每 $k$ 个单位要缴纳 $1$ 单位
不足 $1$ 单位按 $1$ 单位来算

$$D(u) \xrightarrow{x=\frac{D(u)+x}{K}} D(u)+x$$

$$\begin{gathered} (K-1)x = D(u) \Leftrightarrow x = \frac{D(u)}{K-1} \\ \ \\ \text{rhs} = D(u) + x = \textbf{ceil}(\frac{D(u)}{K-1} \cdot K) \end{gathered}$$

• $\text{run dijkstra}(), \ \textbf{get} \ D_{to}$
  $\textbf{for} \ \forall e(x, y)$
  $~~~~~~$$\textbf{if} \ D(y) > D_{to}, D(y)=D_{to}, p(y) = e(x, y)$
  $~~~~~~$$\textbf{if} \ D(y) = D_{to}, \ ([x_1, x_2], y), \ x_2 < x_1$
  $~~~~~~~~~~$$(x_1, y) \rightarrow (x_2, y), \quad p(y) = e(x_2, y)$

• $\text{output path}$
  $~~~~~~$$\text{run dijkstra}(ed\rightarrow st)$
  $~~~~~~$$\text{out}(ed \leftarrow st)$
  $~~~~~~$$\text{out}(u, V(p(u)), V(p(p(u))), \cdots)$

const int maxn = 100 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, P, st, ed;

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
    int from, to, isUp;
    Edge() {}
    Edge(int f, int t, int w) : from(f), to(t), isUp(w) {}
};

vector<Edge> edges;

class Node {
public:
    int u;
    ll dist;
    Node() {}
    Node(int u, ll d) : u(u), dist(d) {}
    bool operator< (const Node& rhs) const {
        return dist > rhs.dist;
    }
};

void initG() {
    edges.clear();
    _for(i, 0, maxn) G[i].clear();
}

void addEdge(int u, int v, int isUp) {
    edges.push_back(Edge(u, v, isUp));
    G[u].push_back(edges.size() - 1);
}
// == Graph finsihed ==

inline int read() {
    char ch[9];
    scanf("%s", ch);
    if(isupper(ch[0])) return ch[0] - 'A';
    else return ch[0] - 'a' + 26;
}

inline char format(int u) {
    return u < 26 ? 'A' + u : 'a' + (u - 26);
}

inline bool isUp(int u) {
    return u < 26 ? 1 : 0;
}

// == dijkstra ==
ll D[maxn];
int vis[maxn];
int pid[maxn];

void initDij(ll P, int st) {
    _for(i, 0, maxn) D[i] = inf;
    D[st] = P;
    Set(vis, 0);
    Set(pid, 0);
    pid[st] = -1;
}

void dijkstra(ll P, int st) {
    initDij(P, st);
    priority_queue<Node> que;
    que.push(Node(st, P));

    while (!que.empty()) {
        int x = que.top().u;
        que.pop();
        //debug(D[x]);
        if(vis[x]) continue;
        vis[x] = 1;

        _for(i, 0, G[x].size()) {
            const Edge& e = edges[G[x][i]];
            int y = e.to;

            ll d_to;
            if(e.isUp) d_to = (ll)ceil(D[x] * 1.0 / 19 * 20);
            else d_to = D[x] + 1;
            //debug(d_to);

            if(D[y] > d_to || (D[y] == d_to && format(x) < format(edges[pid[y]].from))) {
                D[y] = d_to;
                pid[y] = G[x][i];
                que.push(Node(y, D[y]));
            }
        }
    }
}

void print(int u) {
    if(pid[u] == -1) {
        printf("%c\n", format(u));
        return;
    }
    printf("%c-", format(u));
    print(edges[pid[u]].from);
}
// == dijkstra finsihed ==

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d", &n) == 1 && n >= 0) {
        initG();
        printf("Case %d:\n", ++kase);

        // build graph
        _for(i, 0, n) {
            int u = read();
            int v = read();

            if(u != v) {
                addEdge(u, v, isUp(u));
                addEdge(v, u, isUp(v));
            }
        }
        // graph finished

        // then dijkstra
        scanf("%d", &P);
        st = read();
        ed = read();
        //debug(ed);

        dijkstra(P, ed);
        printf("%lld\n", D[st]);
        print(st);
    }
}