图算法和图模型(二)

这部分我重点写了最短路问题

最短路

Dijkstra

const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 5;

// == Graph definition ==
vector<int> G[maxn];
class Edge {
public:
    int to, weight;
    Edge() {}
    Edge(int to, int w) : to(to), 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);
}
// == Graph finished ==

int st[maxn], ed[maxn], w[maxn];
typedef pair<int, int> PII;
int n, m;

// == Dijkstra ==
int vis[maxn], dist[maxn];

void initDij() {
    Set(dist, inf);
    Set(vis, 0);
    dist[1] = 0;
}

void dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII> > que;
    que.push(MPR(0, 1));

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

        _for(i, 0, G[x].size()) {
            int y = edges[G[x][i]].to;
            int z = edges[G[x][i]].weight;

            if(dist[y] > dist[x] + z) {
                dist[y] = dist[x] + z;
                que.push(MPR(dist[y], y));
            }
        }
    }
}
// == Dijkstra finished ==

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

    int kase;
    scanf("%d", &kase);
    while (kase--) {
        scanf("%d%d", &n, &m);

        initG();
        _rep(i, 1, m) {
            scanf("%d%d%d", &st[i], &ed[i], &w[i]);
            addEdge(st[i], ed[i], w[i]);
        }

        initDij();
        dijkstra();

        ll sum = 0;
        _rep(i, 1, n) sum += dist[i];

        initG();
        _rep(i, 1, m) addEdge(ed[i], st[i], w[i]);

        initDij();
        dijkstra();

        _rep(i, 1, n) sum += dist[i];

        printf("%lld\n", sum);
    }
}

Moore-Bellman-Ford

bellmanford

$\text{bellman-ford 方程的应用，求平均权值最小}$
$\text{对于某个权值} \ c , \ c \in [0, maxv]$
$\text{二分猜想最小平均权值为} \ mid$

$\begin{gathered} w_1+w_2+\cdots w_k < k \cdot mid \\ \Leftrightarrow (w_1-mid)+(w_2-mid)+\cdots +(w_k-mid) <0 \\ \ \\ \textbf{将}\ w(a, b) \Leftarrow w(a, b)-mid \\ \text{用 bellman-ford 判负环} \end{gathered}$

$\textbf{i)} \quad LHS < k \cdot mid < k \cdot (maxv+1)$
$\text{如果对于} \ mid = maxv + 1 \ \text{都找不到，那么}$
$\text{负圈不存在，因为有负圈，平均权值必然} < maxv +1$

$\textbf{ii)} \quad L = 0, \ R = maxv$
二分， $test()=(w_1-mid)+\cdots +(w_k-mid)$
目标，找到 $test()$ 最大值

$\left\{\begin{array}{l}\text { test }<0, \quad \text { test } \uparrow, \text { mid } \downarrow, \quad R=\text {mid} \\ \text { test }>0, \quad \text { test } \downarrow, \text { mid } \uparrow, \quad L=\text {mid}\end{array}\right.$

本例中，因为是判负环，开始时
$[0, n-1]$ 每个顶点都可能作为起点，进入队列
所以一开始

for(int i = 0; i < n; i++) {
    dist[i] = 0;
    que.push(i), inq[i] = true;
}

然后根据 $\text{bellman-ford}$ 方程
将边 $\text{relax } n$ 次，迭代 $n$ 次

const int inf = 0x3f3f3f3f;
const int maxn = 1000;
const double eps = 1e-3;
int n, m;

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

// == bellman ford algorithm ==
bool inq[maxn];
int cnt[maxn], p[maxn];
double dist[maxn];

void initBellman() {
    Set(inq, 0);
    Set(cnt, 0);
    Set(p, 0);
}


bool bellmanFord() {
    initBellman();

    queue<int> que;
    _for(i, 0, n) {
        dist[i] = 0;
        que.push(i);
        inq[i] = true;
    }

    while (!que.empty()) {
        int x = que.front();
        inq[x] = false;
        que.pop();

        _for(i, 0, G[x].size()) {
            int y = edges[G[x][i]].to;
            double z = edges[G[x][i]].weight;

            if(dist[y] > dist[x] + z) {
                dist[y] = dist[x] + z;
                p[y] = G[x][i];

                if(!inq[y]) {
                    inq[y] = true;
                    que.push(y);
                    if(++cnt[y] > n) return true;
                }
            }
        }
    }
    return false;
}
// == bellman finished ==

// == test ==
bool test(double x) {
    _for(i, 0, edges.size()) edges[i].weight -= x;
    bool ans = bellmanFord();

    _for(i, 0, edges.size()) edges[i].weight += x;

    return ans;
}
// == test finsihed ==

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

    for(int _ = 1; _ <= kase; _++) {
        printf("Case #%d: ", _);

        scanf("%d%d", &n, &m);
        initG();
        double maxv = 0;
        while (m--) {
            int u, v;
            double w;
            scanf("%d%d%lf", &u, &v, &w);
            u--; v--; maxv = max(maxv, w);

            addEdge(u, v, w);
        }

        // bellman ford judge cycle
        if(!test(maxv + 1)) printf("No cycle found.\n");
        else {
            double L = 0, R = maxv;
            while (R - L > 1e-3) {
                double mid = L + (R - L) / 2;
                if(test(mid)) R = mid;
                else L = mid;
            }
            printf("%.2lf\n", L);
        }
    }
}

最短路综合

双端队列bfs

POJ3662
POJ3662


const int maxn = 1000 + 5;
const int inf = 0x3f3f3f3f;
int n, P, K;

// == 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);
}
// == Graph finsihed ==

// == bfs shortest path ==
deque<int> que;
int dist[maxn];
bool vis[maxn];

void initbfs() {
    Set(dist, inf);
    dist[1] = 0;
    Set(vis, 0);
}

int bfs(int mid) {
    initbfs();
    que.push_back(1);

    while (!que.empty()) {
        int x = que.front();
        que.pop_front();

        if(vis[x]) continue;
        vis[x] = 1;

        _for(i, 0, G[x].size()) {
            int y = edges[G[x][i]].to;
            int z = edges[G[x][i]].weight;

            if(vis[y]) continue;
            if(z > mid) {
                // weight count as 1
                if(dist[y] > dist[x] + 1) {
                    dist[y] = dist[x] + 1;
                    que.push_back(y);
                }
            }
            else {
                // weight count as 0
                if(dist[y] > dist[x]) {
                    dist[y] = dist[x];
                    que.push_front(y);
                }
            }
        }
    }
    return dist[n];
}
// == bfs finished ==

int main() {
    freopen("input.txt", "r", stdin);
    initG();
    cin >> n >> P >> K;

    int maxl = -1;
    _rep(i, 1, P) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z);
        addEdge(y, x, z);
        maxl = max(maxl, z);
    }

    // deque bfs to solve shortest path
    if(bfs(maxl + 1) > K) {
        puts("-1");
        return 0;
    }

    int l = 0, r = maxl;
    while (l < r) {
        int mid = (l + r) >> 1;
        if(bfs(mid) > K) l = mid + 1;
        else r = mid;
    }
    cout << l << endl;
}

dp视角

Acwing340
POJ3662-02

const int N = 1000 + 5;
const int P = 10000 + 5;
const int maxn = N * N;
const int inf = 0x3f3f3f3f;
int n, p, k;

// == 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);
}

inline int _hash(int x, int p) {
    return x + p * n;
}
// == Graph finished ==

// == spfa ==
int d[maxn];
bool inq[maxn];
int cnt[maxn];
queue<int> que;

void initSpfa() {
    Set(d, inf);
    d[1] = 0;
    Set(inq, 0);
    Set(cnt, 0);
}

bool spfa() {
    initSpfa();

    que.push(1);
    inq[1] = true;

    while (!que.empty()) {
        int x = que.front();
        que.pop();
        inq[x] = false;

        _for(i, 0, G[x].size()) {
            int y = edges[G[x][i]].to;
            int z = edges[G[x][i]].weight;

            if(d[y] > max(d[x], z)) {
                d[y] = max(d[x], z);

                if(!inq[y]) {
                    que.push(y);
                    inq[y] = true;
                    if(++cnt[y] > n) return true;
                }
            }
        }
    }
    return false;
}
// == spfa finsihed ==

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> p >> k;
    initG();

    _rep(i, 1, p) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);

        _rep(j, 0, k) {
            addEdge(_hash(x, j), _hash(y, j), z);
            addEdge(_hash(y, j), _hash(x, j), z);
        }
        _for(j, 0, k) {
            addEdge(_hash(x, j), _hash(y, j + 1), 0);
            addEdge(_hash(y, j), _hash(x, j + 1), 0);
        }
    }

    // bellman ford
    spfa();
    if(d[n + k * n] == inf) puts("-1");
    else cout << d[n + k * n] << endl;
}

最短路的应用

输出路径

$st \longrightarrow (\Box_a \leftrightarrow \Box_b)\longrightarrow ed$
最短路径的构成是
$(st \longrightarrow \Box_a) \ \cup \ (a,b) \ \cup \ (\Box_b \longrightarrow ed)$
其中 $(\Box_b \longrightarrow ed)$ 进行反向处理

// path[b] 表示 (st->b) 路径上的所有点
// (st, b0, b1, ..., b)
_forDown(j, path2.size() - 1, 0)
    path.push_back(path2[b][j])

$d(a):= \text{shortest path of } (st \longrightarrow a)$
$d(b):= \text{shortest path of } (ed \longrightarrow b)$
$ans = \min \{d(a) + d(b) + T(a, b)\}$

const int maxn = 1000 + 10;
const int inf = 0x3f3f3f3f;
int N, S, E, K, M;

// == 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) {}
};
vector<Edge> edges;

void initG(int N) {
    _rep(i, 0, N) 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 ==
int dist[maxn], p[maxn];
bool vis[maxn];
typedef pair<int, int> PII;

void initDij(int s) {
    Set(vis, 0);
    Set(dist, inf);
    dist[s] = 0;
}
void dijkstra(int s) {
    initDij(s);
    priority_queue<PII, vector<PII>, greater<PII> > que;
    que.push(MPR(0, s));

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

        _for(i, 0, G[x].size()) {
            int y = edges[G[x][i]].to;
            int z = edges[G[x][i]].weight;

            if(dist[y] > dist[x] + z) {
                dist[y] = dist[x] + z;
                p[y] = G[x][i];
                que.push(MPR(dist[y], y));
            }
        }
    }
}
// == dijkstra finished ==

// == get path ==
vector<int> path1[maxn], path2[maxn];
int d1[maxn], d2[maxn];

// (s, a0, ..., a) <- (a, ak, ak-1, ..., a0, s)
void prework(int s, vector<int> path[], int d[]) {
    dijkstra(s);
    _rep(i, 1, N) {
        d[i] = dist[i];

        for(int t = i; t != s; t = edges[p[t]].from) path[i].push_back(t);
        path[i].push_back(s);
        reverse(path[i].begin(), path[i].end());
    }
}
// == prework finsihed ==

// == solve the problem ==
void solve() {
    int ans = d1[E];
    vector<int> path = path1[E];
    int mid = -1;

    scanf("%d", &K);
    _for(i, 0, K) {
        int X, Y, Z;
        scanf("%d%d%d", &X, &Y, &Z);

        _for(_, 0, 2) {
            if(ans > d1[X] + d2[Y] + Z) {
                ans = d1[X] + d2[Y] + Z;

                path = path1[X];
                _forDown(j, path2[Y].size() - 1, 0) {
                    path.push_back(path2[Y][j]);
                }

                mid = X;
            }
            swap(X, Y);
        }
    }

    _for(i, 0, path.size() - 1) printf("%d ", path[i]);
    printf("%d\n", E);

    if(mid == -1) printf("Ticket Not Used\n");
    else printf("%d\n", mid);

    printf("%d\n", ans);
}
// == solve finsihed ==

// init ans
void init(int n) {
    _rep(i, 0, n) {
        path1[i].clear();
        path2[i].clear();
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d%d%d", &N, &S, &E) == 3) {
        scanf("%d", &M);
        init(N);

        // build graph
        initG(N);
        _for(i, 0, M) {
            int X, Y, Z;
            scanf("%d%d%d", &X, &Y, &Z);
            addEdge(X, Y, Z);
            addEdge(Y, X, Z);
        }

        // prework
        prework(S, path1, d1);
        prework(E, path2, d2);

        // solve the problem
        if(kase != 0) printf("\n");
        kase++;

        solve();
    }
}

建反向图

LibreOJ2590

用 $D(x)$ 表示买入操作， $F[x]$ 表示卖出操作
那么很显然，要让差价最大
$D(x):= \min(cost(st \rightarrow x))$
$F(x)$ 表示卖出操作，研究对象显然是 $\text{path}:=(x\rightarrow ed)$
如果建一个反图，那么实际上
$F(x):= \max(cost(ed\rightarrow x))$
最后遍历
$\forall x \in G, \ \ \max (F[x] - D[x])$
这个问题可以用 $\text{Dijkstra}$ 解决吗？看状态方程
因为 $D(x)$ 表示从 $st\rightarrow x$ 路径中最小的权值，状态转移如下
$\forall (x,y) \in E(G)$
$\quad \quad D(y) = \min(D(x), c(x,y))$
这里不能用 $\text{Dijkstra}$
$D(y) = \min(D(x), price(y))$
- 假设 $\text{Dijkstra}$ 的优先队列中的 $\min \text{top()}$ 为 $x$
  $\text{Dijkstra}$ 循环不变式认为
  $\forall (x, ...)$
  $\quad \quad x$ 是当前最小值
  $\quad \quad$ 之后的遍历只会增大 $D(x)$

来看一个有环图
Wrong
用 $\text{Dijkstra}$ 会得到一个更小的 $D(x_1)$

这里改用 $\textbf{spfa}$

const int maxn = 100000 + 10;
const int inf = 0x3f3f3f3f;
int N, M;
int A[maxn];

// == Graph definition ==
vector<int> G1[maxn];
vector<int> G2[maxn];
class Edge {
public:
    int to;
    Edge() {}
    Edge(int t) : to(t) {}
};
vector<Edge> edges1;
vector<Edge> edges2;

void initG1(int n) {
    _rep(i, 0, n) G1[i].clear();
    edges1.clear();
}

void initG2(int n) {
    _rep(i, 0, n) G2[i].clear();
    edges2.clear();
}

void addEdge1(int u, int v) {
    edges1.push_back(Edge(v));
    G1[u].push_back(edges1.size() - 1);
}

void addEdge2(int u, int v) {
    edges2.push_back(Edge(v));
    G2[u].push_back(edges2.size() - 1);
}
// == Graph definition finished ==

// == dijkstra, D[] used min, F[] used max ==
bool inq[maxn];
int D[maxn], F[maxn];

void initSpfa1() {
    Set(inq, 0);
    Set(D, inf);
    D[1] = A[1];
}

void initSpfa2() {
    Set(inq, 0);
    Set(F, -inf);
    F[N] = A[N];
}


void spfa1() {
    initSpfa1();
    queue<int> que1;
    que1.push(1);
    inq[1] = true;

    while (!que1.empty()) {
        int x = que1.front();
        que1.pop();
        inq[x] = false;

        _for(i, 0, G1[x].size()) {
            int y = edges1[G1[x][i]].to;
            if(D[x] < inf && D[y] > min(D[x], A[y])) {
                D[y] = min(D[x], A[y]);
                if(!inq[y]) {
                    que1.push(y);
                    inq[y] = true;
                }
            }
        }
    }
}

void spfa2() {
    initSpfa2();
    queue<int> que2;
    que2.push(N);
    inq[N] = 1;

    while (!que2.empty()) {
        int x = que2.front();
        que2.pop();
        inq[x] = false;

        _for(i, 0, G2[x].size()) {
            int y = edges2[G2[x][i]].to;
            if(F[x] > -inf && F[y] < max(F[x], A[y])) {
                F[y] = max(F[x], A[y]);
                if(!inq[y]) {
                    que2.push(y);
                    inq[y] = true;
                }
            }
        }
    }
}
// == dijkstra finished ==

int main() {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
    initG1(N);
    initG2(N);

    // get price data A[]
    _rep(i, 1, N) scanf("%d", &A[i]);

    // build Graph
    _rep(i, 1, M) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addEdge1(x, y);
        addEdge2(y, x);

        if(z == 2) {
            addEdge1(y, x);
            addEdge2(x, y);
        }
    }

    // dijkstra
    spfa1();
    spfa2();

    int Ans = 0;
    _rep(i, 1, N) Ans = max(Ans, F[i] - D[i]);
    cout << Ans << endl;
}

复习：dfs找连通块

void dfs(int x, int cnt) {
    belong[x] = cnt;
    _for(i, 0, G[x].size()) {
        int y = edges[G[x][i]].to;
        if(belong[y]) continue;
        dfs(y);
    }
}
_rep(i, 1, n) {
    if(!belong[i]) {
        cnt++;
        dfs(i, cnt);
    }
}

负权边处理

LibreOJ10081

负权的问题，可以先根据连通分量缩点

将正权边根据连通分量缩点，生成点集 $V$
添加含有负权的边，构成有向无环图
有向无环图根据拓扑排序，找到单源最短路径
$\forall v \in V$ ，缩点后的每个连通分量，用 $\text{dijkstra}$

算法描述 $\forall x \in V$

$\text{dfs}$ 统计 $belong[x]$ ，即连通分量编号
添加有向边，同时计数 $deg[belong[x]]$

在 $\text{Dijkstra}$ 的时候加入拓扑排序
$\text{que}$ 用于拓扑排序，优先队列 $\text{pque}$ 用于 $\text{Dijkstra}$

所有入度为 $0$ 的点进入 $\text{que}$ , 这里用的点集是缩点后的
当然于此同时， $D(st) = 0, D(V/st) = \infty$
执行 $\text{Dijkstra}$ 主过程
$\forall x \in V(G), \forall (x,y) \in E(G)$
每走一条边，都得检查 $belong[x] =? belong[y]$
如果 $belong[x] \neq belong[y]$ , $\text{dijkstra}$ 不走 $(x,y)$
$(x,y)$ 可能是负权边，也可能不是，但总之不要丢掉
$--deg[belong[y]] == 0, \ \textbf{then} \ \text{que}.push(belong[y])$
重复上述步骤直到 $\text{ que }$ 中没有元素

特别注意，因为 $\textbf{S}$ 不一定是 $deg[ \ ] == 0$ 的点
初始化的时候， $\text{que}.push(belong[S])$


const int maxn = 25000 + 10;
const int inf = 0x3f3f3f3f;
const int INF = 0x7f;
int N, R, P, S;

// == 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);
}
// == Graph finished ==

// == prework ==
// usage: prework(N) to calculate connect component
int cnt = 0;
int belong[maxn];
void dfs(int x, int cnt) {
    belong[x] = cnt;
    _for(i, 0, G[x].size()) {
        int y = edges[G[x][i]].to;
        if(belong[y]) continue;
        dfs(y, cnt);
    }
}

void prework(int N) {
    _rep(i, 1, N) {
        if(!belong[i]) {
            ++cnt;
            dfs(i, cnt);
        }
    }
}
// == prework finished ==

// == use for topo sort ==
int deg[maxn];
// == topo finsihed ==

// == dijkstra with top ==
int dist[maxn];
bool vis[maxn];
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > pque;
queue<int> que;

void initDij() {
    Set(vis, 0);
    Set(dist, INF);
    dist[S] = 0;
    que.push(belong[S]);
}

void dijkstra() {
    initDij();
    _rep(i, 1, cnt) if(deg[i] == 0) que.push(i);

    while (!que.empty()) {
        int c = que.front();
        que.pop();
        _rep(i, 1, N) if(belong[i] == c) pque.push(MPR(dist[i], i));

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

            _for(i, 0, G[x].size()) {
                int y = edges[G[x][i]].to;
                int z = edges[G[x][i]].weight;
                if(dist[y] > dist[x] + z) {
                    dist[y] = dist[x] + z;
                    if(belong[x] == belong[y]) pque.push(MPR(dist[y], y));
                }

                if(belong[x] != belong[y] && --deg[belong[y]] == 0) que.push(belong[y]);
            }
        }
    }
}
// == dijkstra finsiehd ==

void init() {
    cnt = 0;
    Set(belong, 0);
    Set(deg, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    cin >> N >> R >> P >> S;

    // build Graph
    initG();
    _rep(i, 1, R) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z);
        addEdge(y, x, z);
    }
    prework(N);
    // build negative Graph
    _rep(i, 1, P) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z);
        if(belong[x] != belong[y]) ++deg[belong[y]];
    }

    // topo and dijkstra
    dijkstra();
    _rep(i, 1, N) {
        if(dist[i] >= inf) puts("NO PATH");
        else printf("%d\n", dist[i]);
    }
}