图算法和图模型(四)

这篇博文主要讲述了最短路算法中
可能会用得到的建图技巧

隐式图Dijkstra

隐式图 $\text{Dijkstra}$ 的核心在于，一边 $\text{Dijkstra}$ 一边建图
$\forall u \in V(G), u$ 一般情况表示状态编码

$\textbf{algorithm}$
$\textbf{u(state,} \ \textbf{dist)}$

• $\text{get start status}$
  $\text{que}\leftarrow\text{st(stateCode, 0)}$
• $\textbf{while(que.size())}$

  • $\text{get u = que.front(), que.pop()}$
    $\text{if u = endState, return } \textbf{D(u)}$

  • $\textbf{for} \ \forall i \in \text{candidates}$
    $~~~~~~$$\text{check}(edges(i)) \text{ is available?}$
    $~~~~~~$$\text{if(check == false and not available) } continue$
    $~~~~~~$$\text{get } \textbf{v(newState} \ \textbf{,} \ \textbf{u.dist} \ + \textbf{e(u,} \ \textbf{v))}$
    $~~~~~~$$\text{sometimes change v.state}$
    $~~~~~~$$D(v) = \min(D(v), v.dist)$
    $~~~~~~$$~~~~$$\text{if changed, que.push}(v)$

const int maxn = 20;
const int maxm = 100 + 5;
const int inf = 0x3f3f3f3f;
int T[maxm];
int n, m;

// == node definition ==
class Node {
public:
    int state, dist;
    bool operator< (const Node& rhs) const {
        return dist > rhs.dist;
    }
    Node() {}
    Node(int s, int d) : state(s), dist(d) {}
};

int D[1<<maxn], vis[1<<maxn];
char before[maxm][maxn], after[maxm][maxn];

void initG() {
    Set(D, inf);
    Set(vis, 0);
}
// == node finished ==

// == Dijkstra ==
bool valid(const Node& u, const int k) {
    // check before patches k
    _for(i, 0, n) {
        if(before[k][i] == '-' && ((1<<i) & u.state)) return false;
        if(before[k][i] == '+' && !((1<<i) & u.state)) return false;
    }
    return true;
}

int dijkstra() {
    priority_queue<Node> que;
    Node st((1<<n)-1, 0);
    que.push(st);
    D[st.state] = 0;

    while (!que.empty()) {
        Node x = que.top(); que.pop();
        if(x.state == 0) return D[x.state];
        if(vis[x.state]) continue;
        vis[x.state] = 1;

        // get next y
        _rep(i, 1, m) {
            bool patchable = valid(x, i);
            if(!patchable) continue;

            // use patches i
            Node y(x.state, x.dist + T[i]);
            _for(j, 0, n) {
                if(after[i][j] == '+') y.state |= (1<<j);
                if(after[i][j] == '-') y.state &= ~(1<<j);
            }

            if(D[y.state] > y.dist) {
                D[y.state] = y.dist;
                que.push(y);
            }
        }
    }
    return -1;
}
// == Dijkstra finsihed ==

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d%d", &n, &m) == 2 && n) {
        initG();
        _rep(i, 1, m) scanf("%d%s%s", &T[i], before[i], after[i]);
        printf("Product %d\n", ++kase);

        // then solve the problem
        int ans = dijkstra();
        if(ans < 0) printf("Bugs cannot be fixed.\n\n");
        else printf("Fastest sequence takes %d seconds.\n\n", ans);
    }
}

状态依赖的Dijkstra

如果边加入一个时间维度，规定在某个时间段内可以走
$\forall e \in E(G)$
$\quad [0, a]:= \text{pass}$
$\quad [a+1, a+b]:= \text{can not pass}$

$\textbf{algorithm}$
$\textbf{u(id,} \ \textbf{dist)}, D(V)=\infty$

• $\text{get st}$
  $\text{que} \leftarrow\text{st(s, 0), D(s) = 0}$

• $\textbf{while(que.size())}$
  $~~~~~~$$\text{get u = que.front(), que.pop()}$
  $~~~~~~$$\text{check } \forall e(u, v) \in E(G)$
  $~~~~~~$$\text{if } e.t > e.a, \text{could not pass, } continue$

  $~~~~~~$$\textbf{for} \ \forall e(u, v)$
  $~~~~~~$$~~~~$$\textbf{check}\ D(u) \stackrel{?}\longleftrightarrow [0,e.a] \cup [e.a+1, e.a+e.b]$
  $~~~~~~$$~~~~$$D(u) \equiv r \pmod{e.a+e.b}$

  $~~~~~~$$~~~~$$r + e.t \in [0, e.a], \quad w(u, v):= e.t$
  $~~~~~~$$~~~~$$r+e.t > e.a, \quad w(u, v):= (e.a+e.b-r) + e.t$
  $~~~~~~$$~~~~$$D(v) = \min(D(v), D(u) + w)$
  $~~~~~~$$~~~~~~~~$$\text{if changed, que} \leftarrow v$

const int maxn = 300 + 10;
const int inf = 0x3f3f3f3f;
int n, m, s, t;
int D[maxn], vis[maxn];

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

class Edge {
public:
    int from, to, a, b, t;
    Edge(int from, int to, int a, int b, int t) : from(from), to(to), a(a), b(b), t(t) {}
    Edge() {}
};

vector<Edge> edges;

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

void initG(int s) {
    Set(D, inf);
    D[s] = 0;
    Set(vis, 0);
}
// == Graph finished ==

// == Dijkstra ==
struct Node {
    int u, dist;
    Node(int u, int d) : u(u), dist(d) {}
    Node() {}
    bool operator< (const Node& rhs) const {
        return dist > rhs.dist;
    }
};

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

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

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

            int w, r = D[x] % (e.a + e.b);
            if(r + e.t <= e.a) w = e.t;
            else w = e.a + e.b - r + e.t;

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

void init() {
    _rep(i, 0, n) G[i].clear();
    edges.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (~scanf("%d%d%d%d", &n, &m, &s, &t)) {
        init();
        printf("Case %d: ", ++kase);

        // get data
        _for(i, 0, m) {
            int u, v, a, b, t;
            scanf("%d%d%d%d%d", &u, &v, &a, &b, &t);
            addEdge(u, v, a, b, t);
        }

        // then dijkstra
        initG(s);
        dijkstra(s);
        printf("%d\n", D[t]);
    }
}

动态规划统计最短路条数

$\textbf{algorithm}$

• $\text{run} \ \textbf{Dijkstra()} \ \text{and calculate } \forall u \in V(G) \rightarrow D(u)$
• $f(k, u)$ 表示以 $D(u)+k$ 作为最短路的路径条数
  $~~~~~~$$[D(u), k]$ 表示此时的 $u$ 点的长度为 $D(u) + k$
  $~~~~~~$$\forall e(u, v) :=$

$$\begin{gathered} [D(u),k]\Rightarrow\left\{\begin{array}{lc} \{f(1, v)+=f(0, u)\} \cup \{f(k, v)+=f(k, u)\}, \quad k=0 \\ \{f(k, v)+=f(k, u)\} , \quad k = 1 \end{array}\right. \end{gathered}$$

$$\begin{gathered} D(v) = D(u) + w(u, v) \quad \rightarrow f(k, v) += f(k, u) \\ D(v)+1 = D(u) + w(u, v) \quad \rightarrow f(1, v) += f(0, u) \end{gathered}$$

$$f(0, s) = 1$$

const int maxn = 1e3 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, st, ed;

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

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

vector<Edge> edges;

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

void initG(int st) {
    _for(i, 0, maxn) D[i] = inf;
    D[st] = 0;
    Set(vis, 0);
}
// == Graph finished ==

// == Dijkstra ==
struct Node {
    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 dijkstra(int 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] = true;

        _for(i, 0, G[x].size()) {
            const Edge& e = edges[G[x][i]];
            int y = e.to;
            if(D[y] > D[x] + 1ll * e.w) {
                D[y] = D[x] + 1ll * e.w;
                que.push(Node(y, D[y]));
            }
        }
    }
}
// == Dijkstra finished ==

// == dp ==
ll f[2][maxn];
bool cmp(int a, int b) {
    return D[a] < D[b];
}
int ord[maxn];

void initDp() {
    Set(f, 0);
    f[0][st] = 1ll;
    _rep(i, 1, n) ord[i] = i;
    sort(ord + 1, ord + 1 + n, cmp);
}

void dp() {
    _for(k, 0, 2) _rep(i, 1, n) {
        int x = ord[i];
        _for(j, 0, G[x].size()) {
            const Edge& e = edges[G[x][j]];
            int y = e.to;
            if(D[y] == D[x] + e.w) f[k][y] += f[k][x];
            if(k == 0 && D[y] + 1 == D[x] + e.w) f[1][y] += f[0][x];
        }
    }
}

// == dp finsiehd ==

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

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

        // input data
        _for(i, 0, m) {
            int u, v, l;
            scanf("%d%d%d", &u, &v, &l);
            addEdge(u, v, l);
        }
        scanf("%d%d", &st, &ed);


        // dijkstra
        initG(st);
        dijkstra(st);

        // then dp
        initDp();
        dp();

        printf("%lld\n", f[0][ed] + f[1][ed]);
    }
}