图算法和图模型(七)

这篇文章继续对最短路问题做相关阐述
主要讲一下负权边的处理
以及状态图建图的技巧和方法

多阶段 Dijkstra

看一下这个例子的建图过程

$\textbf{algorithm}$

$\text{build graph}$
$\textbf{for} \ \forall \text{trip} \in [1, \text{NI}]$
$~~~~~~$ $\text{get trip List} \rightarrow ([\textbf{toList}], len)$
$~~~~~~$ $\text{chooseTicket}([\textbf{toList}, len])$
$\text{chooseTicket}(\textbf{toList}, len):$
$~~~~~~$ $\textbf{for} \ \forall i \in [0, \text{NT}), \ \textbf{for} \ \forall k \in [1, tot]$
$~~~~~~~~~~$ $\textbf{st}=(k,\text{tickets[i,0]})$
$~~~~~~~~~~$ $\textbf{for} \ \forall j \in [1, \text{tickets}(i).\text{size)}$
$~~~~~~~~~~~~~~$ $\textbf{if} \ \ \textbf{toList}[k]=\text{tickets}[i,j], \textbf{Edge}(\textbf{st}, (k+1, \text{tickets[i, j]}), \text{cost})$
$~~~~~~~~~~~~~~$ $\textbf{else} \ \textbf{Edge}(\textbf{st}, (k, \text{tickets}[i, j], \text{cost})$
$~~~~~~~~~~~~~~$ $\text{cost}:=(\text{price}[ith\text{-Tickets}], \text{ticketID})$
$\text{run } \textbf{Dijkstra}()$

bash


const int maxN = 4000 + 10;
const int inf = 0x3f3f3f3f;
int nCities = 0;
const int maxn = 100;
vector<int> tickets[maxn];
int cost[maxn];
int NT, NI;

// == Graph ==
vector<int> G[maxN];

class Edge {
public:
    int from, to, weight, val;
    Edge() {}
    Edge(int u, int v, int w, int val) : from(u), to(v), weight(w), val(val) {}
};

class Node {
public:
    int u, dist;
    Node() {}
    Node(int u, int dist) : u(u), dist(dist) {}
    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, int val) {
    edges.push_back(Edge(u, v, w, val));
    G[u].push_back(edges.size() - 1);
}
// == Graph finsihed ==

// == dijkstra ==
int D[maxN], vis[maxN];
int pid[maxN];

void initDij(int st) {
    _for(i, 0, maxN) D[i] = inf;
    D[st] = 0;

    Set(vis, 0);
    Set(pid, 0);
}

void dijsktra(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;
                pid[y] = G[x][i];
                que.push(Node(y, D[y]));
            }
        }
    }
}

vector<int> getPath(int ed, const int st) {
    vector<int> path;
    while (ed != st) {
        path.push_back(edges[pid[ed]].val);
        ed = edges[pid[ed]].from;
    }
    reverse(path.begin(), path.end());
    return path;
}
// == dijkstra finsihed ==

// == get all tickets ==
map<int, int> cityID;

inline int ID(int x) {
    if(cityID.count(x)) return cityID[x];
    cityID[x] = ++nCities;
    return nCities;
}

inline int ID(int i, int j) {
    return (i - 1) * nCities + j;
}

void getTickets(const int NT) {
    _for(i, 0, NT) {
        tickets[i].clear();
        int len;
        scanf("%d%d", &cost[i], &len);
        while (len--) {
            int x;
            scanf("%d", &x);
            tickets[i].push_back(ID(x));
        }
    }
}
// == get tickets finished ==

// == get trip data ==
vector<int> toList;
int getTrip(const int trip) {
    toList.clear();
    int tot = 0;
    scanf("%d", &tot);

    _for(i, 0, tot) {
        int x;
        scanf("%d", &x);
        toList.push_back(ID(x));
    }

    return tot;
}
// == trip finished ==

// == chooseTicket for trip ==
void chooseTicket(const vector<int>& toList, const int tot) {
    _for(i, 0, NT) _rep(k, 1, tot) {
        int cur = tickets[i][0];
        int k2 = k;

        _for(j, 1, tickets[i].size()) {
            int A = tickets[i][j];
            if(A == toList[k2]) k2++;
            if(k2 > tot) break;

            addEdge(ID(k, cur), ID(k2, A), cost[i], i + 1);
            if(k2 == tot) break;
        }
    }
}
// == chooseTicket finished ==

void init() {
    nCities = 0;
    cityID.clear();
    _for(i, 0, maxn) tickets[i].clear();
    Set(cost, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d", &NT) == 1 && NT) {
        init();

        // get tickets
        getTickets(NT);
        scanf("%d", &NI);
        kase++;

        _rep(trip, 1, NI) {
            int tot = getTrip(trip);
            assert(toList.size() != 0);

            initG();
            chooseTicket(toList, tot);
            int src = ID(1, toList[0]), ed = ID(tot, toList[tot-1]);
            dijsktra(src);

            printf("Case %d, Trip %d: Cost = %d\n", kase, trip, D[ed]);
            printf("  Tickets used:");

            vector<int> res = getPath(ed, src);
            _for(i, 0, res.size()) printf(" %d", res[i]);
            printf("\n");
        }
    }
}

状态建图

UVALive3661

$\textbf{algorithm}$
$\textbf{build} \ \textbf{graph}$

$\text{get vector}$

\begin{gathered} \quad \{\textbf{top,} \ \textbf{bottom} \ \} \ \{\textbf{left,} \ \textbf{right} \ \} \{ \textbf{slash} \} = (i, j, dir[0, 2)) \\ \ \\ \xrightarrow{\text{vector}} \textbf{[edges]} \end{gathered}

$u=\textbf{ID(edges)}=\textbf{ID}(\textbf{top}(i,j,dir), \cdots)$
$v=\textbf{ID}(\textbf{edges}) = \textbf{ID}(\textbf{slash}(i, j, dir))$
$add(u, v, cost(\textbf{slash}(i, j, dir)))$

$\textbf{dijkstra}$

$\textbf{st} = 0, \ add(\textbf{0}, \textbf{leftBorder})$
$add(\textbf{0,} \ \textbf{bottomBorder})$

$\textbf{ed} \ \textbf{right}=$
$~~~~~~$ $\textbf{for} \ \forall i \in [0, n)$
$~~~~~~~~~~$ $\textbf{ID}(i, m-1, dir=1)$

$\textbf{ed} \ \textbf{top}=$
$~~~~~~$ $\textbf{for} \ \forall i \in [0, m)$
$~~~~~~~~~~$ $\textbf{ID}(0, i, dir = 0)$
$\text{run } dijkstra()$
$\textbf{ans} = \min (\textbf{D[ed} \ \textbf{right],} \ \textbf{D[ed} \ \textbf{top]})$

bash

const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 10;
const int maxN = 4000000;
int cost[maxn][maxn][3];
int n, m;

// == Graph definition ==
vector<int> G[maxN];
class Edge {
public:
    int to, weight;
    Edge() {}
    Edge(int to, int w) : to(to), 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(v, w));
    G[u].push_back(edges.size() - 1);
}
// == 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 finsihed ==

inline int ID(int i, int j, int dir) {
    return i*m+j+1 + dir*n*m;
}

inline int read() {
    int x;
    scanf("%d", &x);
    return x;
}

// == build graph ==
void getEdge(int *e1, int *e2, int *e3) {
    int *edges[3] = {e1, e2, e3};
    // edges[i]:= (i, j, dir)
    _for(i, 0, 3) _for(j, 0, 3) if(i != j) {
        int u = ID(edges[i][0], edges[i][1], edges[i][2]);
        int v = ID(edges[j][0], edges[j][1], edges[j][2]);
        int w = cost[edges[j][0]][edges[j][1]][edges[j][2]];

        addEdge(u, v, w);
    }
}

void build() {
    _for(i, 0, n - 1) _for(j, 0, m - 1) {
        int top[] = {i, j, 0};
        int bottom[] = {i + 1, j, 0};
        int left[] = {i, j, 1};
        int right[] = {i, j + 1, 1};
        int slash[] = {i, j, 2};

        getEdge(top, right, slash);
        getEdge(bottom, left, slash);
    }

    _for(i, 0, n - 1) {
        int u = ID(i, 0, 1);
        int w = cost[i][0][1];
        addEdge(0, u, w);
    }
    _for(i, 0, m - 1) {
        int u = ID(n - 1, i, 0);
        int w = cost[n - 1][i][0];
        addEdge(0, u, w);
    }
}
// == build finsiehd ==

void init() {
    Set(cost, 0);
}

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

        // get data
        _for(i, 0, n) _for(j, 0, m-1) cost[i][j][0] = read();
        _for(i, 0, n - 1) _for(j, 0, m) cost[i][j][1] = read();
        _for(i, 0, n - 1) _for(j, 0, m - 1) cost[i][j][2] = read();

        // build graph
        build();

        // dijkstra
        dijkstra(0);

        // get ans
        int ans = inf;
        _for(i, 0, n - 1) ans = min(ans, D[ID(i, m - 1, 1)]);
        _for(i, 0, m - 1) ans = min(ans, D[ID(0, i, 0)]);

        //debug(ans);

        printf("Case %d: Minimum = %d\n", ++kase, ans);
    }
}

最短路和dp

ZOJ1232

$\textbf{run} \ floyd()$
$f(i,j) \leftarrow f(i, k) + f(k, j)$
$~~~~~~$ $\textbf{if} \ k \in [1,A], D[i,j] \leqslant L$
$~~~~~~~~~~$ $(\text{st} \rightarrow k) \text{ can use magic boot}, \ \textbf{valid}(i, j) = 1$
$\textbf{dp} \ \textbf{equation}$

\begin{gathered} dp(i,k)=\min\left\{\begin{gathered} \forall j<i, & d p(j, k-1) && \text {valid}(i, 1)=1 \\ \forall {j<i}, & d p(j, k)+D(j\rightarrow i) \end{gathered}\right. \end{gathered}

$\text{dp algorithm}$
$\textbf{st:=}$
$~~~~~~$ $\textbf{for} \ \forall i \in V, dp(i, 0) = D(st, i)$
$~~~~~~$ $\textbf{for} \ \forall k \in [0, K], dp(st, k) = 0$
$\textbf{ed:=}$
$~~~~~~$ $\text{dp}(ed, K)$

bash

const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;
int D[maxn][maxn];
int valid[maxn][maxn];
int a, b, m, L, K;

void init() {
    Set(D, inf);
    _for(i, 0, maxn) D[i][i] = 0;

    Set(valid, 0);
}

void build() {
    _for(i, 0, m) {
        int u, v, L;
        scanf("%d%d%d", &u, &v, &L);
        D[u][v] = D[v][u] = min(D[v][u], L);
    }
}

void floyd() {
    _rep(k, 1, a+b) _rep(i, 1, a+b) _rep(j, 1, a+b) {
        if(D[i][j] > D[i][k] + D[k][j]) {
            D[i][j] = D[i][k] + D[k][j];
        }
        if(k <= a && D[i][j] <= L) valid[i][j] = 1;
    }
}

// == dp ==
const int st = 1;
int dp[maxn][maxn];

void initDP() {
    Set(dp, inf);
    _rep(i, 1, a+b) dp[i][0] = D[st][i];
    _rep(k, 0, K) dp[st][k] = 0;
}

void solve() {
    _rep(i, 1, a+b) _rep(k, 1, K) {
        _for(j, 1, i) {
            if(valid[i][j] == 1)
                dp[i][k] = min(dp[i][k], dp[j][k - 1]);
            dp[i][k] = min(dp[i][k], dp[j][k] + D[j][i]);
        }
    }
}
// == dp finished ==

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

    while (kase--) {
        init();
        scanf("%d%d%d%d%d", &a, &b, &m, &L, &K);

        // build
        build();

        // floyd
        floyd();

        // dp
        initDP();
        solve();

        printf("%d\n", dp[a+b][K]);
    }
}

最短路和dp（二）

这里的状态转移比较特殊
在每一个节点 $u$ , 加油，必须一升一升加

\textbf{state}(u, gas, cost)

x(u, g a s, cost) \rightarrow\left\{\begin{gathered} x(u, g a s+1, cost+p(u)) && g a s+1 \leqslant c \\ x((u \rightarrow v), g a s-w(u, v), cost) && g a s-w(u, v) \geqslant 0 \end{gathered}\right.

$\textbf{algorithm}$
$\text{run } dijkstra()$
$~~~~~~$ $\textbf{vis}(u, gas) = 1\text{ , mark node complete}$

bash

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

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

class Edge {
public:
    int from, to, weight;
    Edge() {}
    Edge(int u, int v, int w) : from(u), to(v), 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(u, v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == Dijkstra ==
class State {
public:
    int u, gas, cost;
    bool operator< (const State& rhs) const {
        return cost > rhs.cost;
    }

    State() {}
    State(int u, int g, int c) : u(u), gas(g), cost(c) {}
};

int vis[maxn][maxn];
int ans = inf;

void initDij(int st, const int C) {
    Set(vis, 0);
    ans = inf;
}

bool dijkstra(int st, int ed, const int C) {
    initDij(st, C);
    priority_queue<State> que;
    que.push(State(st, 0, 0));

    while (!que.empty()) {
        State x = que.top();
        que.pop();

        if(x.u == ed) {
            ans = x.cost;
            return true;
        }

        if(vis[x.u][x.gas]) continue;
        vis[x.u][x.gas] = 1;

        if(x.gas + 1 <= C) {
            State nxt(x.u, x.gas + 1, x.cost + P[x.u]);
            que.push(nxt);
        }
        _for(i, 0, G[x.u].size()) {
            const Edge& e = edges[G[x.u][i]];
            int y = e.to;

            if(x.gas >= e.weight) {
                State nxt(y, x.gas - e.weight, x.cost);
                que.push(nxt);
            }
        }
    }
    return false;
}
// == Dijkstra finsihed ==

void init() {
    Set(P, 0);
}

void solve() {
    int q;
    scanf("%d", &q);
    while (q--) {
        int st, ed, C;
        scanf("%d%d%d", &C, &st, &ed);
        if(dijkstra(st, ed, C)) printf("%d\n", ans);
        else printf("impossible\n");
    }
}

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

    initG();
    init();
    // get data
    _for(i, 0, n) scanf("%d", &P[i]);
    _for(i, 0, m) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    // each query, dijkstra
    solve();
}

最短路拓展

UVA11280

$\textbf{algorithm:} \ \text{Dijkstra}(st)$

\textbf{state}(u, k) \quad \text{k denotes } \textbf{number} \ \textbf{of} \ \textbf{stays}

$\textbf{for} \ \forall e(x, y)$
$~~~~~~$ $D(y, k+1) \leftarrow D(x, k) + w(x, y)$

$st\rightarrow ed, \text{ query}(S)$
$\textbf{start:=} (st, 0)$
$\textbf{end:=} \ \textbf{for} \ \forall k \in [1, S]$
$~~~~~~~~~~$ $\textbf{ans} \ \textbf{=} \ \min(D(ed, k))$

bash

const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
int tot = 0;
map<string, int> id;
int n, m;

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

class Edge {
public:
    int from, to, weight;
    Edge() {}
    Edge(int u, int v, int w) : from(u), to(v), 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(u, v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == Dijkstra ==
class State {
public:
    int u, k, dist;
    State() {}
    State(int u, int k, int dist) : u(u), k(k), dist(dist) {}

    bool operator< (const State& rhs) const {
        return dist > rhs.dist;
    }
};


int vis[maxn][maxn];
int D[maxn][maxn];

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

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

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

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

            if(D[y][x.k+1] > D[x.u][x.k] + e.weight) {
                D[y][x.k+1] = D[x.u][x.k] + e.weight;
                que.push(State(y, x.k+1, D[y][x.k+1]));
            }
        }
    }
}
// == Dijkstra finished ==

inline void getID(const string& str) {
    if(id.count(str)) return;
    else {
        id[str] = ++tot;
        return;
    }
}

void solve() {
    int q;
    scanf("%d", &q);
    while (q--) {
        int S;
        scanf("%d", &S);

        int ans = inf;
        _rep(k, 1, S + 1) ans = min(ans, D[n][k]);

        //debug(ans);
        if(ans != inf) printf("Total cost of flight(s) is $%d\n", ans);
        else printf("No satisfactory flights\n");
    }
}

void init() {
    tot = 0;
    id.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);

    _rep(kase, 1, T) {
        printf("Scenario #%d\n", kase);
        init();
        initG();

        // get city data
        scanf("%d", &n);
        _for(i, 0, n) {
            string str;
            cin >> str;
            getID(str);
        }
        // get flights data
        scanf("%d", &m);
        _for(i, 0, m) {
            string from, to;
            int w;
            cin >> from >> to >> w;
            int u = id[from], v = id[to];
            //debug(u), debug(v), debug(w), puts("");

            addEdge(u, v, w);
        }
        // get query
        dijkstra(1);
        solve();
        if(kase != T) cout << endl;
    }
}