【数据结构】图的操作与应用

防止复制粘贴，代码还是结束之后补上。

更难了，但是感觉不如函数题盲调。

函数题#

三道题都是板子，一定知道该怎么做，接下来就是如何驯服指针了。

邻接矩阵存储图的深度优先遍历#

1
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ) {
2
    if (Visited[V]) return;
3
    Visited[V] = true;
4
    Visit(V);
5
    for (int i = 0; i < Graph->Nv; ++i) {
6
        if (i != V && Graph->G[V][i] != INFINITY) DFS(Graph, i, Visit);
7
    }
8
}

邻接表存储图的广度优先遍历#

1
typedef struct _node {
2
    Vertex val;
3
    struct _node *ne;
4
} Node;
5
Node *h, *t;
6

7
int empty() {
8
    return h == NULL;
9
}
10

11
void push(Vertex val) {
12
    Node *p = (Node *)malloc(sizeof(Node));
13
    p->val = val, p->ne = NULL;
14
    if (empty()) h = t = p;
15
    else t->ne = p, t = p;
16
}
17

18
Vertex pop() {
19
    Node *p = h;
20
    h = h->ne;
21
    if (!h) t = NULL;
22
    return p->val;
23
}
24

25
void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ) {
26
    Visited[S] = true;
27
    push(S);
28
    while (!empty()) {
29
        Vertex x = pop();
30
        Visit(x);
31
        for (PtrToAdjVNode iter = Graph->G[x].FirstEdge; iter; iter = iter->Next) {
32
            Vertex y = iter->AdjV;
33
            if (!Visited[y]) {
34
                Visited[y] = true;
35
                push(y);
36
            }
37
        }
38
    }
39
}

Count Connected Components#

1
int vis[MaxVertexNum];
2

3
void dfs(int x, LGraph Graph) {
4
    if (vis[x]) return;
5
    vis[x] = true;
6
    for (PtrToAdjVNode iter = Graph->G[x].FirstEdge; iter; iter = iter->Next) {
7
        dfs(iter->AdjV, Graph);
8
    }
9
}
10

11
int CountConnectedComponents( LGraph Graph ) {
12
    int res = 0;
13
    for (int i = 0; i < Graph->Nv; ++i) {
14
        if (!vis[i]) {
15
            dfs(i, Graph);
16
            res++;
17
        }
18
    }
19
    return res;
20
}

编程题#

公路村村通#

最小生成树板子，我用了 Kruskal。

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
const int N = 1010, M = 3010;
7

8
int fa[N];
9

10
int getfa(int x) {
11
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
12
}
13

14
struct Edge {
15
    int w, x, y;
16
} ed[M];
17

18
int main() {
19
    int n, m;
20
    scanf("%d%d", &n, &m);
21
    for (int i = 1; i <= n; ++i) {
22
        fa[i] = i;
23
    }
24
    for (int i = 1; i <= m; ++i) {
25
        scanf("%d%d%d", &ed[i].x, &ed[i].y, &ed[i].w);
26
    }
27
    sort(ed + 1, ed + m + 1, [](Edge a, Edge b) {
28
        return a.w < b.w;
29
    });
30
    int t = 0, res = 0;
31
    for (int i = 1; i <= m; ++i) {
32
        int x = getfa(ed[i].x), y = getfa(ed[i].y);
33
        if (x == y) continue;
34
        t++;
35
        res += ed[i].w;
36
        fa[y] = x;
37
    }
38
    if (t != n - 1) printf("-1\n");
39
    else printf("%d\n", res);
40
    return 0;
41
}

城市间紧急救援#

惊现天梯赛 L2 题，而且还不是那种比较水的 L2。

也算是裸的 Dijkstra 板子，但是维护的东西太多了初学非常容易挂，设城市驻扎人数为 a，路径长度为 dis，途径救援队人数最多为 f，最短路条数为 cnt，边权为 e，前驱为 pre，更新的思路是

$dis_y > dis_x + e$ ，说明之前的都不在最短路上，直接全部覆盖 $dis_y = dis_x + e,\ f_y = f_x + a_y, \ cnt_y = cnt_x,\ pre_y = x$
$dis_y = dis_x + e \land f_y > f_x + a_y$ ，之前的最短路不满足 f 最优覆盖 f 和前驱，之前的 cnt 仍然是最短路，所以累加 cnt， $\ f_y = f_x + a_y, \ cnt_y += cnt_x,\ pre_y = x$
$dis_y = dis_x + e \land f_y \le f_x + a_y$ 当前这几条不满足 f 的最优性，但是仍然可能是最短路，只更新 cnt， $cnt_y += cnt_x$ 。

之后还涉及一个根据 pre 输出路径的问题，第一次写也容易出问题。

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <cstring>
5

6
using namespace std;
7

8
const int N = 500;
9

10
int a[N], dis[N], f[N], pre[N], cnt[N];
11
bool vis[N];
12
vector<pair<int, int>> ed[N];
13

14
void print(int x) {
15
    if (pre[x] != -1) {
16
        print(pre[x]);
17
        printf(" %d", x);
18
    }
19
    else printf("%d", x);
20
}
21

22
int main() {
23
    int n, m, s, d;
24
    scanf("%d%d%d%d", &n, &m, &s, &d);
25
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
26
    for (int i = 0; i < m; ++i) {
27
        int x, y, z;
28
        scanf("%d%d%d", &x, &y, &z);
29
        ed[x].emplace_back(z, y);
30
        ed[y].emplace_back(z, x);
31
    }
32
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
33
    memset(dis, 0x3f, sizeof(dis));
34
    memset(pre, -1, sizeof(pre));
35
    dis[s] = 0;
36
    cnt[s] = 1;
37
    f[s] = a[s];
38
    q.emplace(dis[s], s);
39
    while (!q.empty()) {
40
        int x = q.top().second;
41
        q.pop();
42
        if (vis[x]) continue;
43
        vis[x] = true;
44
        for (auto [e, y] : ed[x]) {
45
            if (dis[y] > dis[x] + e) {
46
                dis[y] = dis[x] + e;
47
                cnt[y] = cnt[x];
48
                f[y] = f[x] + a[y];
49
                pre[y] = x;
50
                q.emplace(dis[y], y);
51
            }
52
            else if (dis[y] == dis[x] + e) {
53
                if (f[y] < f[x] + a[y]) {
54
                    f[y] = f[x] + a[y];
55
                    pre[y] = x;
56
                }
57
                cnt[y] += cnt[x];
58
            }
59
        }
60
    }
61
    printf("%d %d\n", cnt[d], f[d]);
62
    print(d);
63
    printf("\n");
64
    return 0;
65
}

关键活动#

拓扑排序dp，记完成任务 i 最短时间为 f_i，关于关键路径，我的思路是对于每个点，给耗时最大的那几条路径的入边建个反图，dp 出结果之后找到 f 最大的点在建的反图跑一遍 bfs，途经的边全标上，然后排序输出。

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <tuple>
5
#include <algorithm>
6

7
using namespace std;
8

9
const int N = 110;
10

11
vector<tuple<int, int, int>> ed[N];
12
vector<pair<int, int>> rev[N];
13
vector<tuple<int, int, int>> res;
14
int deg[N], f[N];
15
bool v[N];
16

17
int main() {
18
    int n, m, t = 0;
19
    scanf("%d%d", &n, &m);
20
    for (int i = 1; i <= m; ++i) {
21
        int x, y, z;
22
        scanf("%d%d%d", &x, &y, &z);
23
        ed[x].emplace_back(z, i, y);
24
        deg[y]++;
25
    }
26
    queue<int> q;
27
    for (int i = 1; i <= n; ++i) {
28
        if (deg[i] == 0) q.emplace(i);
29
    }
30
    while (!q.empty()) {
31
        int x = q.front();
32
        q.pop();
33
        t = max(t, f[x]);
34
        for (auto [e, i, y] : ed[x]) {
35
            if (f[y] < f[x] + e) {
36
                f[y] = f[x] + e;
37
                rev[y] = {{i, x}};
38
            }
39
            else if (f[y] == f[x] + e) {
40
                rev[y].emplace_back(i, x);
41
            }
42
            if (--deg[y] == 0) q.emplace(y);
43
        }
44
    }
45
    bool flag = true;
46
    for (int i = 1; i <= n; ++i)
47
        if (deg[i]) {
48
            flag = false;
49
            break;
50
        }
51
    if (flag) {
52
        printf("%d\n", t);
53
        for (int i = 1; i <= n; ++i) {
54
            if (f[i] == t) {
55
                v[i] = true;
56
                q.emplace(i);
57
            }
58
        }
59
        while (!q.empty()) {
60
            int x = q.front();
61
            q.pop();
62
            for (auto [i, y] : rev[x]) {
63
                res.emplace_back(y, x, i);
64
                if (v[y]) continue;
65
                v[y] = true;
66
                q.emplace(y);
67
            }
68
        }
69
        sort(res.begin(), res.end(), [](tuple<int, int, int> a, tuple<int, int, int> b) {
70
            return get<0>(a) == get<0>(b) ? get<2>(a) > get<2>(b) : get<0>(a) < get<0>(b);
71
        });
72
        for (auto [a, b, _] : res) {
73
            printf("%d->%d\n", a, b);
74
        }
75
    }
76
    else {
77
        printf("0\n");
78
    }
79
    return 0;
80
}

Star's Blog